fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. using namespace __gnu_pbds;
  7.  
  8. template<class T> using oset = 
  9.             tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  10.  
  11. #define ll long long
  12. #define ld long double
  13. #define ar array
  14. #define vi vector<int>
  15. #define vii vector<vector<int>>
  16. #define pii pair<int, int>
  17. #define pb push_back
  18. #define all(x) x.begin(), x.end()
  19. #define f first
  20. #define s second
  21. #define endl "\n"
  22.  
  23. const int MOD = 1e9+7;
  24. const int inf = 1e9;
  25. const ll linf = 1e18;
  26.  
  27. const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
  28. const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
  29.  
  30. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  31.  
  32.  
  33. // -------------------------------------------------- Main Code --------------------------------------------------
  34.  
  35. const int N = 3e5+5, SQRT = 633;
  36. int n, arr[N], tin[N], tout[N], parent[N][25], depth[N], Time = 0, contains[N], counter[N];
  37. vi g[N], tour;
  38. vector<array<int, 5>> queries;
  39. string ans[N];
  40.  
  41. void dfs(int src, int par) {
  42.     tin[src] = ++Time;
  43.     tour.pb(src);
  44.  
  45.     // bin lifting table
  46.     parent[src][0] = par;
  47.     for (int i = 1; i < 25; i++) parent[src][i] = parent[parent[src][i-1]][i-1];
  48.  
  49.     for (auto ch : g[src]) {
  50.         if (ch == par) continue;
  51.         depth[ch] = depth[src]+1;
  52.         dfs(ch, src);
  53.     }
  54.     tour.pb(src);
  55.     tout[src] = ++Time;
  56. }
  57.  
  58. int LCA(int a, int b) {
  59.     if (depth[a] < depth[b]) swap(a, b);
  60.     int dis = depth[a]-depth[b];
  61.     for (int i = 0; i < 25; i++) if (dis&(1<<i)) a = parent[a][i];
  62.  
  63.     if (a == b) return a;
  64.  
  65.     for (int i = 24; i >= 0; i--) {
  66.         if (parent[a][i] != parent[b][i]) a = parent[a][i], b = parent[b][i];
  67.     }
  68.  
  69.     return parent[a][0];
  70. }
  71.  
  72. void update(int node) {
  73.     contains[node] ? counter[arr[node]]-- : counter[arr[node]]++;
  74.     contains[node] = !contains[node];
  75. }
  76.  
  77. void reset() {
  78.     Time = 0;
  79.     tour.clear();
  80.     queries.clear();
  81.     for (int i = 0; i <= n; i++) {
  82.         arr[i] = 0;
  83.         tin[i] = 0;
  84.         tout[i] = 0;
  85.         for (int j = 0; j <= 24; j++) parent[i][j] = 0;
  86.         depth[i] = 0; contains[i] = 0; counter[i] = 0;
  87.         g[i].clear();
  88.         ans[i] = "";
  89.     }
  90. }
  91.  
  92. void sol() {
  93.     reset();
  94.     tour.pb(0);
  95.     int q; cin >> q;
  96.     for (int i = 1; i <= n; i++) cin >> arr[i];
  97.     for (int i = 1; i <= n-1; i++) {
  98.         int a, b; cin >> a >> b;
  99.         g[a].pb(b);
  100.         g[b].pb(a);
  101.     }
  102.  
  103.     dfs(1, 0);
  104.  
  105.     for (int i = 1; i <= q; i++) {
  106.         int a, b, c; cin >> a >> b >> c;
  107.         if (tin[a] > tin[b]) swap(a, b);
  108.         int l, r, lca = -1;
  109.         if (tin[a] <= tin[b] && tout[a] >= tout[b]) l = tin[a], r = tin[b];
  110.         else l = tout[a], r = tin[b], lca = LCA(a, b);
  111.         queries.pb({l, r, c, i, lca});
  112.     }
  113.  
  114.     sort(all(queries), [&](array<int, 5> &x, array<int, 5> &y) {
  115.         int l1 = x[0], r1 = x[1], l2 = y[0], r2 = y[1];
  116.         if (l1/SQRT == l2/SQRT) return r1 < r2;
  117.         return l1/SQRT < l2/SQRT;
  118.     });
  119.  
  120.     int prevL = 1, prevR = 0;
  121.     for (auto i : queries) {
  122.         int l = i[0], r = i[1], k = i[2], idx = i[3], lca = i[4];
  123.  
  124.         if (prevR < r) for (int i = prevR+1; i <= r; i++) update(tour[i]);
  125.         else for (int i = prevR; i > r; i--) update(tour[i]);
  126.  
  127.         if (prevL < l) for (int i = prevL; i < l; i++) update(tour[i]);
  128.         else for (int i = prevL-1; i >= l; i--) update(tour[i]);
  129.  
  130.         if (lca != -1) update(lca);
  131.         ans[idx] = (((counter[k])>0)?"Find":"NotFind");
  132.         if (lca != -1) update(lca);
  133.  
  134.         prevL = l, prevR = r;
  135.     }
  136.  
  137.     for (int i = 1; i <= q; i++) cout << ans[i] << endl;
  138. }
  139.  
  140. int main () {
  141.     ios_base::sync_with_stdio(false);
  142.     cin.tie(NULL);
  143.  
  144.     while (cin >> n) {
  145.         sol();
  146.     }
  147.     return 0;
  148. }
Success #stdin #stdout 0.01s 21232KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ZdZFLF
problem GOT, based on SPOJ submission 31901500 (CPP), 2023-09-25 19:08:59
language:
C++ (gcc 8.3)
created:
2 years 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!