vlatkovski

snowcow fail

Apr 17th, 2021
390
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. Failure:
  3. Can't do lazy propagation on MainTree.
  4.  
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9. typedef pair<int, int> pii;
  10.  
  11. const int N = 100100;
  12. const int Q = 100100;
  13.  
  14. int n, q;
  15. vector<int> graph[N];
  16. pair<int, int> queries[Q];
  17.  
  18. int timer;
  19. int tin[N], tout[N];
  20.  
  21. void dfs(int node, int par) {
  22.     tin[node] = timer++;
  23.     for (int to : graph[node]) {
  24.         if (to == par) continue;
  25.         dfs(to, node);
  26.     }
  27.     tout[node] = timer-1;
  28. }
  29.  
  30. struct ColorManager {
  31.     struct PosHandler {
  32.         vector<int> pos;
  33.         inline void comp_all() {
  34.             sort(pos.begin(), pos.end());
  35.             pos.erase(unique(pos.begin(), pos.end()), pos.end());
  36.         }
  37.         inline int get_comp(int i) {
  38.             return lower_bound(pos.begin(), pos.end(), i) - pos.begin();
  39.         }
  40.     } poshandler[N];
  41.     int cbegin[N];
  42.     int vecsize;
  43.     int vec[2*Q];
  44.     typedef pair<int, bool> Node;
  45.     Node tree[8*Q];
  46.     void build() {
  47.         vecsize = 1;
  48.         vec[0] = 0;
  49.         for (int c = 1; c <= n; ++c) {
  50.             poshandler[c].comp_all();
  51.             cbegin[c] = vecsize;
  52.             vecsize += poshandler[c].pos.size();
  53.             for (int j = cbegin[c], i = 0; j < vecsize; ++j, ++i) {
  54.                 vec[j] = poshandler[c].pos[i];
  55.             }
  56.         }
  57. //      for (int i = 0; i < 8*Q; ++i) {
  58. //          tree[i].first = 0;
  59. //          tree[i].second = false;
  60. //      }
  61.         cout<<"CH: vecsize="<<vecsize<<"\n";
  62.         cout<<"CH: i: ";
  63.         for (int i = 1; i < vecsize; ++i) cout << i << " ";
  64.         cout<<"\nCH: c: ";
  65.         for (int c = 1; c <= n; ++c) {
  66.             for (int i = cbegin[c]; i-cbegin[c] < (int)poshandler[c].pos.size(); ++i) {
  67.                 cout << c << " ";
  68.             }
  69.         }
  70.         cout << "\nCH: a: ";
  71.         for (int c = 1; c <= n; ++c) {
  72.             for (int i = cbegin[c]; i-cbegin[c] < (int)poshandler[c].pos.size(); ++i) {
  73.                 cout << vec[i] << " ";
  74.             }
  75.         }
  76.         cout << "\n";
  77.     }
  78.     inline void update(int c, int l, int r) {
  79.         l = cbegin[c] + poshandler[c].get_comp(l);
  80.         r = cbegin[c] + poshandler[c].get_comp(r);
  81.         cout << "  CM: starting update c="<<c<<" l="<<l<<" r="<<r<<"\n";
  82.         update(1, 1, vecsize-1, l, r);
  83.     }
  84.     inline int query(int c, int l, int r) {
  85.         l = cbegin[c] + poshandler[c].get_comp(l);
  86.         r = cbegin[c] + poshandler[c].get_comp(r);
  87.         return query(1, 1, vecsize-1, l, r);
  88.     }
  89.     inline void push(Node &v, Node &l, Node &r, int tl, int tr) {
  90.         if (!v.second) return;
  91.         int tm = (tl + tr) / 2;
  92.         l.first = vec[tm] - vec[tl] + 1;
  93.         l.second = true;
  94.         r.first = vec[tr] - vec[tm+1] + 1;
  95.         r.second = true;
  96.         v.second = false;
  97.     }
  98.     void update(int v, int tl, int tr, int l, int r) {
  99.         if (l > r) return;
  100.         if (l == tl && tr == r) {
  101.             tree[v].first = vec[tr] - vec[tl] + 1;
  102.             cout<<"   CM: updated ["<<l<<","<<r<<"], first="<<tree[v].first<<"\n";
  103.             tree[v].second = true;
  104.             return;
  105.         }
  106.         push(tree[v], tree[2*v], tree[2*v+1], tl, tr);
  107.         int tm = (tl + tr) / 2;
  108.         update(2*v, tl, tm, l, min(r, tm));
  109.         update(2*v+1, tm+1, tr, max(l, tm+1), r);
  110.         tree[v].first = tree[2*v].first + tree[2*v+1].first;
  111.     }
  112.     int query(int v, int tl, int tr, int l, int r) {
  113.         if (l > r) return 0;
  114.         if (l <= tl && tr <= r) return tree[v].first;
  115.         push(tree[v], tree[2*v], tree[2*v+1], tl, tr);
  116.         int tm = (tl + tr) /2;
  117.         return  query(2*v, tl, tm, l, min(r, tm))
  118.                 + query(2*v+1, tm+1, tr, max(l, tm+1), r);
  119.     }
  120. } cmanager;
  121.  
  122. struct MainTree {
  123.     typedef pair<int, int> Node;
  124.     Node tree[4*N];
  125.     void build() {
  126. //      for (int i = 0; i < 4*N; ++i) {
  127. //          tree[i] = 0;
  128. //      }
  129.     }
  130.     inline void update(int c, int l, int r) {
  131. //      cout << "MT: starting update c="<<c<<" l="<<l<<" r="<<r<<"\n";
  132.         return update(1, 1, n, l, r, c);
  133.     }
  134.     inline int query(int l, int r) {
  135.         cout << "MT: starting query l="<<l<<" r="<<r<<"\n";
  136.         return query(1, 1, n, l, r);
  137.     }
  138.     inline void push(Node &v, Node &l, Node &r) {
  139.  
  140.     }
  141.     void update(int v, int tl, int tr, int l, int r, int c) {
  142.         if (l > r) return;
  143.         if (l == tl && tr == r) {
  144.             int old = cmanager.query(c, l, r);
  145.             tree[v].first += r-l+1 - old;
  146.             /*
  147.             Failure.
  148.             */
  149.             //tree[v].second += r-l+1 - old;
  150.             cout << " MT: updated c="<<c<<" l="<<l<<" r="<<r<<" CMQ="<<old<<" res="<<tree[v]<<"\n";
  151.             cmanager.update(c, l, r);
  152.             return;
  153.         }
  154.         push(tree[v], tree[2*v], tree[2*v+1]);
  155.         int tm = (tl + tr) / 2;
  156.         update(2*v, tl, tm, l, min(r, tm), c);
  157.         update(2*v+1, tm+1, tr, max(l, tm+1), r, c);
  158.         tree[v] = tree[2*v] + tree[2*v+1];
  159.     }
  160.     int query(int v, int tl, int tr, int l, int r) {
  161.         if (l > r) return 0;
  162.         if (l <= tl && tr <= r) return tree[v];
  163.         push(tree[v], tree[2*v], tree[2*v+1]);
  164.         int tm = (tl + tr) / 2;
  165.         return  query(2*v, tl, tm, l, min(r, tm))
  166.                 + query(2*v+1, tm+1, tr, max(l, tm+1), r);
  167.     }
  168. } maintree;
  169.  
  170. int main() {
  171.     cin.tie(0)->sync_with_stdio(0);
  172.     #ifndef _DEBUG
  173.     freopen("snowcow.in", "r", stdin);
  174.     freopen("snowcow.out", "w", stdout);
  175.     #endif // _DEBUG
  176.     cin >> n >> q;
  177.     for (int i = 0; i < n-1; ++i) {
  178.         int a, b;
  179.         cin >> a >> b;
  180.         graph[a].push_back(b);
  181.         graph[b].push_back(a);
  182.     }
  183.     timer = 1;
  184.     dfs(1, -1);
  185.     for (int node = 1; node <= n; ++node) {
  186.         cout << node << " -> ["<<tin[node]<<", "<<tout[node]<<"]\n";
  187.     }
  188.     for (int i = 0; i < q; ++i) {
  189.         int type;
  190.         cin >> type;
  191.         if (type == 1) {
  192.             int node, c;
  193.             cin >> node >> c;
  194.             cmanager.poshandler[c].pos.push_back(tin[node]);
  195.             cmanager.poshandler[c].pos.push_back(tout[node]);
  196.             queries[i] = make_pair(node, c);
  197.         } else {
  198.             int node;
  199.             cin >> node;
  200.             queries[i] = make_pair(node, 0);
  201.         }
  202.     }
  203.     cmanager.build();
  204.     maintree.build();
  205.     for (int i = 0; i < q; ++i) {
  206.         int node, c;
  207.         tie(node, c) = queries[i];
  208.         if (c != 0) {
  209.             maintree.update(c, tin[node], tout[node]);
  210.         } else {
  211.             int ans = maintree.query(tin[node], tout[node]);
  212.             cout << ans << '\n';
  213. //          return 0;
  214.         }
  215.     }
  216. }
  217.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×