fork download
copy 
  1. /// Author : Nguyễn Thái Sơn - K18 - KHMT - UIT
  2. /// Training ICPC 2024
  3.  
  4. #include<bits/stdc++.h>
  5.  
  6. /// #pragma GCC optimize("O3,unroll-loops")
  7. /// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  8.  
  9. #define fi first
  10. #define se second
  11. #define TASK "test"
  12. #define pb push_back
  13. #define EL cout << endl
  14. #define Ti20_ntson int main()
  15. #define in(x) cout << x << endl
  16. #define all(x) (x).begin(),(x).end()
  17. #define getbit(x, i) (((x) >> (i)) & 1)
  18. #define cntbit(x) __builtin_popcount(x)
  19. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  20. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  21. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  22.  
  23. using namespace std;
  24.  
  25. typedef long long ll;
  26. typedef vector<int> vi;
  27. typedef pair<int,int> vii;
  28. typedef unsigned long long ull;
  29. typedef vector<vector<int>> vvi;
  30. int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
  31.  
  32. const int N = 1e5 + 5;
  33. const int oo = INT_MAX;
  34. const int mod = 1e9 + 7;
  35. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  36. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  37.  
  38. int val[N], Q, n;
  39. vector<int> dsk[N];
  40. map<string, int> mp;
  41. int cnt;
  42. vector<pair<int, int>> Queries[N];
  43. set<int> S[N];
  44.  
  45. inline void Read_Input() {
  46.     cin >> n;
  47.     FOR(i, 1, n) {
  48.         string s;
  49.         int p;
  50.         cin >> s >> p;
  51.  
  52.         dsk[p].push_back(i);
  53.  
  54.         if (mp.find(s) == mp.end()) {
  55.             ++cnt;
  56.             mp[s] = cnt;
  57.             val[i] = cnt;
  58.         }
  59.         else {
  60.             val[i] = mp[s];
  61.         }
  62.     }
  63.     cin >> Q;
  64.     FOR(i, 1, Q) {
  65.         int v, k;
  66.         cin >> v >> k;
  67.         Queries[v].push_back({k, i});
  68.     }
  69.     cnt = 0;
  70. }
  71.  
  72. int sz[N], h[N], ver[N], tin[N], tout[N], ans[N];
  73.  
  74. inline void DFS(int u, int val) {
  75.     sz[u] = 1;
  76.     tin[u] = ++cnt;
  77.     ver[cnt] = u;
  78.     for (int v : dsk[u]) {
  79.         h[v] = h[u] + 1;
  80.         DFS(v, val),
  81.         sz[u] += sz[v];
  82.     }
  83.     tout[u] = cnt;
  84. }
  85.  
  86.  
  87. inline void dfs(int u, bool keep) {
  88.     /// u = 0
  89.     /// no queries here 
  90.  
  91.     int Heavy = -1;
  92.     for (int v : dsk[u])
  93.         if (Heavy == - 1 || sz[v] > sz[Heavy]) Heavy = v;
  94.     for (int v : dsk[u])
  95.         if (v != Heavy) {
  96.             dfs(v, false);
  97.         }
  98.  
  99.     if (Heavy != -1) {
  100.         dfs(Heavy, true);
  101.     }
  102.  
  103.     int Best = 0;
  104.     for (int v : dsk[u])
  105.         if (v != Heavy) {
  106.             FOR(i, tin[v], tout[v]) {
  107.                 int cc = ver[i];
  108.                 /// dinh cc
  109.                 int hi = h[cc];
  110.  
  111.                 /// dinh cc
  112.                 /// do cao h[cc]
  113.                 /// ten = val[cc]
  114.  
  115.                 S[hi].insert(val[cc]);
  116.  
  117.             }
  118.         }
  119.     S[h[u]].insert(val[u]);
  120.     /// u = 3
  121.  
  122.     for (auto[k, i] : Queries[u]) {
  123.         /// có bao nhiêu đỉnh khác nhau ở độ cao cách u = k
  124.  
  125.         /// dộ cao h[] =  h[u] + k
  126.         if (h[u] + k > n) ans[i] = 0;
  127.         else
  128.         ans[i] = S[h[u] + k].size();
  129.  
  130.     }
  131.  
  132.     if (keep == false) {
  133.         FOR(i, tin[u], tout[u]) {
  134.             int cc = ver[i];
  135.             S[h[cc]].erase(val[cc]);
  136.         }
  137.     }
  138. }
  139.  
  140. inline void Solve() {
  141.     DFS(0, 0);
  142.     dfs(0, 1);
  143.     FOR(i, 1, Q)
  144.         cout << ans[i] << endl;
  145. }
  146.  
  147. Ti20_ntson {
  148. //    freopen(TASK".INP","r",stdin);
  149. //    freopen(TASK".OUT","w",stdout);
  150.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  151.     int T = 1;
  152. //    cin >> T;
  153.     while (T -- ) {
  154.         Read_Input();
  155.         Solve();
  156.     }
  157. }
  158.  
  159.  
  160.  
Success #stdin #stdout 0.01s 14980KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/92BGNZ
language:
C++14 (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!