fork download
copy 
  1. /*
  2.     Author: Cadocx
  3.     Codeforces: https://c...content-available-to-author-only...s.com/profile/Kadoc
  4.     VNOJ: oj.vnoi.info/user/Cadoc
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. // input/output
  11. #define fastIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
  12. #define el cout << '\n'
  13. #define debug(x) cout << #x << " = " << x << '\n'
  14. #define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s"
  15. // #pragma GCC optimize("O2", "unroll-loops", "Ofast")
  16. // #pragma GCC target("avx,avx2,fma")
  17. //data type
  18. #define ll long long
  19. #define ull unsigned long long
  20. #define pii pair<int, int>
  21. #define pll pair<ll, ll>
  22. #define piv pair<int, vector<int>>
  23. #define vi vector<int>
  24. #define vl vector<ll>
  25. #define vc vector<char>
  26. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return 1; }; return 0; }
  27. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return 1; }; return 0; }
  28. //STL
  29. #define sz(x) (int)(x).size()
  30. #define FOR(i,l,r) for(auto i = l; i <= r; i++)
  31. #define FORD(i,r,l) for(auto i = r; i >= l; i--)
  32. #define forin(i,a) for(auto i : a)
  33. #define pb push_back
  34. #define eb emplace_back
  35. #define pf push_front
  36. #define all(x) (x).begin(), (x).end()
  37. #define fi first
  38. #define se second
  39. //bitmask
  40. #define bitcnt(n) __builtin_popcount(n)
  41. #define mask(i) (1 << (i))
  42. #define bit(n, i) (((n) >> (i)) & 1)
  43. #define set_on(n, i) ((n) | mask(i))
  44. #define set_off(n, i) ((n) & ~mask(i))
  45. //constant
  46. #define N 100005
  47. #define MOD 1000000007
  48. #define INF 0x3f3f3f3f
  49. #define LINF 0x3f3f3f3f3f3f3f3f
  50. #define base 31
  51. #define Kadoc 0
  52.  
  53. int n, q;
  54. int in[N], out[N], Timer = 0;
  55. int st[2][N * 4], lz[2][N * 4];
  56. vector<int> g[N];
  57.  
  58. void dfs(int u, int p = -1){
  59.     in[u] = ++Timer;
  60.     for(int v:g[u]) if(v != p) dfs(v, u);
  61.     out[u] = Timer;
  62. }
  63.  
  64. void push(int o, int id, int l, int r){
  65.     if(!lz[o][id]) return;
  66.     st[o][id] = lz[o][id];
  67.     if(l != r) lz[o][id * 2] = lz[o][id * 2 + 1] = lz[o][id];
  68.     lz[o][id] = 0;
  69. }
  70.  
  71. void upd(int o, int id, int l, int r, int u, int v, int x){
  72.     push(o, id, l, r);
  73.     if(v < l || r < u) return;
  74.     if(u <= l && r <= v){
  75.         lz[o][id] = x;
  76.         push(o, id, l, r);
  77.         return;
  78.     }
  79.     int m = (l+r)>>1;
  80.     upd(o, id * 2, l, m, u, v, x);
  81.     upd(o, id * 2 + 1, m+1, r, u, v, x);
  82.     st[o][id] = max(st[o][id * 2], st[o][id * 2 + 1]);
  83. }
  84.  
  85. int get(int o, int id, int l, int r, int u, int v){
  86.     push(o, id, l, r);
  87.     if(v < l || r < u) return 0;
  88.     if(u <= l && r <= v) return st[o][id];
  89.     int m = (l+r)>>1;
  90.     return max(get(o, id * 2, l, m, u, v), get(o, id * 2 + 1, m+1, r, u, v));
  91. }
  92.  
  93. void solve(){
  94.     cin >> n;
  95.     FOR(i, 1, n-1){
  96.         int u, v; cin >> u >> v;
  97.         g[u].eb(v);
  98.         g[v].eb(u);
  99.     }
  100.  
  101.     dfs(1);
  102.  
  103.     cin >> q;
  104.     FOR(i, 1, q){
  105.         int op, u; cin >> op >> u;
  106.         if(op == 1){
  107.             // in[u] -> out[u]
  108.             upd(1, 1, 1, n, in[u], out[u], i);
  109.         }
  110.         else if(op == 2){
  111.             // in[u]
  112.             upd(0, 1, 1, n, in[u], in[u], i);
  113.         }
  114.         else{
  115.             // trang thai la 0: la cai thao tac xoa xay sau thao tac them
  116.             // txoa > tthem
  117.             // t0[in[u] -> out[u]] > t1[in[u]]
  118.  
  119.             // trang thai la 1: la cai thoa tac them xay ra sau thac tac xoa
  120.             // txoa < tthem
  121.             // t0[in[u] -> out[u]] < t1[in[u]]
  122.             int t0 = get(0, 1, 1, n, in[u], out[u]);
  123.             int t1 = get(1, 1, 1, n, in[u], in[u]);
  124.             if(t0 >= t1) cout << 0 << '\n';
  125.             else cout << 1 << '\n';
  126.         }
  127.     }
  128. }
  129.  
  130. int main(){
  131.     #define NAME "TASK"
  132.     if(fopen(NAME".inp", "r")){
  133.         freopen(NAME".inp", "r", stdin);
  134.         freopen(NAME".out", "w", stdout);
  135.     }
  136.  
  137.     fastIO;
  138.  
  139.     if(Kadoc){
  140.         int tc; cin >> tc;
  141.         while(tc--){
  142.             solve();
  143.         }
  144.     } else solve();
  145. }
Success #stdin #stdout 0.01s 7084KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PRTx8f
language:
C++14 (gcc 8.3)
created:
1 day 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!