fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ii pair<int, int>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. const int maxn = 5e5;
  12. const ll INF = 1e18;
  13.  
  14. struct segment_tree
  15. {
  16.     ll seg[4 * maxn + 10], lazy[4 * maxn + 10];
  17.     segment_tree()
  18.     {
  19.         memset(seg, 0, sizeof seg);
  20.         memset(lazy, 0, sizeof lazy);
  21.     }
  22.     void push(int id)
  23.     {
  24.         if (lazy[id] == -1) return ;
  25.         seg[id << 1] = seg[id << 1 | 1] = lazy[id];
  26.         lazy[id << 1] = lazy[id << 1 | 1] = lazy[id];
  27.         lazy[id] = -1;
  28.     }
  29.     void update(int id, int l, int r, int u, int v, ll x)
  30.     {
  31.         if (r < u || l > v) return ;
  32.         if (u <= l && r <= v)
  33.         {
  34.             seg[id] = x;
  35.             lazy[id] = x;
  36.             return ;
  37.         }
  38.         int m = l + r >> 1;
  39.         push(id);
  40.         update(id << 1, l, m, u, v, x);
  41.         update(id << 1 | 1, m + 1, r, u, v, x);
  42.         seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
  43.     }
  44.     ll get(int id, int l, int r, int u, int v)
  45.     {
  46.         if (r < u || l > v) return 0;
  47.         if (u <= l && r <= v) return seg[id];
  48.         int m = l + r >> 1;
  49.         push(id);
  50.         ll a = get(id << 1, l, m, u, v);
  51.         ll b = get(id << 1 | 1, m + 1, r, u, v);
  52.         return max(a, b);
  53.     }
  54. };
  55.  
  56. int n, q, beg[maxn + 10], fin[maxn + 10], timer = 0;
  57. ii query[maxn + 10];
  58. vector<int> adj[maxn + 10];
  59. segment_tree a, b;
  60.  
  61. void dfs(int top, int par = -1)
  62. {
  63.     beg[top] = ++timer;
  64.     for (int next_top : adj[top])
  65.         if (next_top != par)
  66.             dfs(next_top, top);
  67.     fin[top] = timer;
  68. }
  69.  
  70. int main()
  71. {
  72.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  73.     if (fopen("WATER_TREE.INP", "r"))
  74.     {
  75.         freopen("WATER_TREE.INP", "r", stdin);
  76.         freopen("WATER_TREE.OUT", "w", stdout);
  77.     }
  78.  
  79.     cin >> n;
  80.     for (int i = 1; i < n; i++)
  81.     {
  82.         int x, y;
  83.         cin >> x >> y;
  84.         adj[x].push_back(y);
  85.         adj[y].push_back(x);
  86.     }
  87.     dfs(1);
  88.     cin >> q;
  89.     for (int i = 1; i <= q; i++)
  90.         cin >> query[i].fi >> query[i].se;
  91.     for (int i = 1; i <= q; i++)
  92.     {
  93.         int t = query[i].fi;
  94.         int v = query[i].se;
  95.         if (t == 1) a.update(1, 1, n, beg[v], fin[v], i);
  96.         if (t == 2) b.update(1, 1, n, beg[v], beg[v], i);
  97.         if (t == 3)
  98.         {
  99.             ll par = a.get(1, 1, n, beg[v], beg[v]);
  100.             ll child = b.get(1, 1, n, beg[v], fin[v]);
  101.             ll res = max(par, child);
  102.             cout << (query[res].fi == 1), el;
  103.         }
  104.     }
  105. }
Success #stdin #stdout 0.02s 80224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZKnryM
language:
C++14 (gcc 8.3)
created:
7 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!