fork download
copy 
  1. #include <iostream>
  2. #include <sstream>
  3. #include <set>
  4. #include <fstream>
  5. #include <algorithm>
  6. #include <cctype>
  7. #include <iomanip>
  8. #include <vector>
  9. #include <map>
  10. #include <queue>
  11. #include <numeric>
  12. #include <string>
  13. #include <cmath>
  14. #include <climits>
  15. #include <stack>
  16. #include <complex>
  17. #include <cstdlib>
  18. #include <cstring>
  19. #include <array>
  20. #include <unordered_map>
  21. #include <unordered_set>
  22. #include <functional>
  23. #include <bitset>
  24. #include <cassert>
  25. #include <tuple>
  26. #include <iterator>
  27. #include <random>
  28. #include <chrono>
  29. #include <list>
  30.  
  31. using namespace std;
  32. typedef long long ll;
  33. typedef long double ld;
  34. const int N = 6e4 + 5;
  35. //const int mod=998244353;
  36. const int mod=1e9+7;
  37.  
  38.  
  39. struct Node {
  40.     int p = 0, c[2] = {0,0};
  41.     bool flip = false;
  42.     int sz = 1;          // size in aux tree (not strictly necessary here but convenient)
  43.     int val = -1;        // actual node value (int)
  44.     int aand = -1;       // aggregated AND over the aux subtree (including this node)
  45.     Node() {}
  46.     Node(int v) {
  47.         p = c[0] = c[1] = 0;
  48.         flip = false;
  49.         sz = 1;
  50.         val = v;
  51.         aand = v;
  52.     }
  53. };
  54.  
  55. struct LinkCutAND {
  56.     vector<Node> t;
  57.     LinkCutAND() {}
  58.     LinkCutAND(int n, const vector<int>& vals = {}) {
  59.         t.assign(n+1, Node());
  60.         for (int i = 1; i <= n; ++i) {
  61.             int v = (i < (int)vals.size()) ? vals[i] : 0;
  62.             t[i] = Node(v);
  63.         }
  64.     }
  65.  
  66.     // utilities
  67.     bool is_root(int x) {
  68.         int p = t[x].p;
  69.         return p == 0 || (t[p].c[0] != x && t[p].c[1] != x);
  70.     }
  71.     int dir(int x) {
  72.         int p = t[x].p;
  73.         if (!p) return -1;
  74.         return t[p].c[1] == x;
  75.     }
  76.  
  77.     void pull(int x) {
  78.         if (!x) return;
  79.         int l = t[x].c[0], r = t[x].c[1];
  80.         t[x].sz = 1;
  81.         if (l) t[x].sz += t[l].sz;
  82.         if (r) t[x].sz += t[r].sz;
  83.         // AND aggregation: neutral element is all-ones (-1)
  84.         int res = t[x].val;
  85.         if (l) res &= t[l].aand;
  86.         if (r) res &= t[r].aand;
  87.         t[x].aand = res;
  88.     }
  89.  
  90.     void apply_flip(int x) {
  91.         if (!x) return;
  92.         t[x].flip ^= 1;
  93.         swap(t[x].c[0], t[x].c[1]);
  94.     }
  95.  
  96.     void push(int x) {
  97.         if (!x) return;
  98.         if (t[x].flip) {
  99.             if (t[x].c[0]) apply_flip(t[x].c[0]);
  100.             if (t[x].c[1]) apply_flip(t[x].c[1]);
  101.             t[x].flip = false;
  102.         }
  103.     }
  104.  
  105.     void rotate(int x) {
  106.         int p = t[x].p;
  107.         int g = t[p].p;
  108.         int dx = (t[p].c[1] == x);
  109.         int b = t[x].c[dx^1];
  110.  
  111.         if (!is_root(p)) {
  112.             if (t[g].c[0] == p) t[g].c[0] = x;
  113.             else if (t[g].c[1] == p) t[g].c[1] = x;
  114.         }
  115.         t[x].p = g;
  116.  
  117.         t[x].c[dx^1] = p;
  118.         t[p].p = x;
  119.  
  120.         t[p].c[dx] = b;
  121.         if (b) t[b].p = p;
  122.  
  123.         pull(p);
  124.         pull(x);
  125.     }
  126.  
  127.     void push_path(int x) {
  128.         if (!x) return;
  129.         if (!is_root(x)) push_path(t[x].p);
  130.         push(x);
  131.     }
  132.  
  133.     void splay(int x) {
  134.         if (!x) return;
  135.         push_path(x);
  136.         while (!is_root(x)) {
  137.             int p = t[x].p;
  138.             int g = t[p].p;
  139.             if (!is_root(p)) {
  140.                 if ((t[p].c[0] == x) ^ (t[g].c[0] == p)) rotate(x);
  141.                 else rotate(p);
  142.             }
  143.             rotate(x);
  144.         }
  145.         pull(x);
  146.     }
  147.  
  148.     // access: make preferred path from root to x, returns last accessed node
  149.     int access(int x) {
  150.         int last = 0;
  151.         for (int v = x; v; v = t[v].p) {
  152.             splay(v);
  153.             // detach right child (preferred child) and attach last
  154.             t[v].c[1] = last;
  155.             pull(v);
  156.             last = v;
  157.         }
  158.         splay(x);
  159.         return last;
  160.     }
  161.  
  162.     void make_root(int x) {
  163.         access(x);
  164.         apply_flip(x);
  165.     }
  166.  
  167.     int find_root(int x) {
  168.         access(x);
  169.         // go to leftmost node
  170.         while (true) {
  171.             push(x);
  172.             if (t[x].c[0]) x = t[x].c[0];
  173.             else break;
  174.         }
  175.         splay(x);
  176.         return x;
  177.     }
  178.  
  179.     bool connected(int u, int v) {
  180.         if (u == v) return true;
  181.         return find_root(u) == find_root(v);
  182.     }
  183.  
  184.     // link u and v (create edge). requires they are in different trees
  185.     bool link(int u, int v) {
  186.         // prevent creating cycle
  187.         if (connected(u, v)) return false;
  188.         make_root(u);
  189.         // now u is root of its tree; set parent pointer to v
  190.         t[u].p = v;
  191.         // no need to update v here; access/pull will handle when needed
  192.         return true;
  193.     }
  194.  
  195.     // cut edge u-v if it exists
  196.     bool cut(int u, int v) {
  197.         make_root(u);
  198.         access(v);
  199.         // now v is splayed and its left child should be u if edge existed and u was direct child
  200.         if (t[v].c[0] != u || t[u].c[1] != 0) return false;
  201.         t[v].c[0] = 0;
  202.         t[u].p = 0;
  203.         pull(v);
  204.         return true;
  205.     }
  206.  
  207.     // set node u's value to x
  208.     void set_val(int u, int x) {
  209.         access(u);
  210.         t[u].val = x;
  211.         pull(u);
  212.     }
  213.  
  214.     int get_val(int u) {
  215.         access(u);
  216.         return t[u].val;
  217.     }
  218.  
  219.     // query bitwise AND along path u..v (includes both endpoints)
  220.     int query_and(int u, int v) {
  221.         if (!connected(u, v)) {
  222.             // if not connected, convention: return neutral element or throw.
  223.             // I'll return -1 (all bits set) if you want identity; but it's better to handle connectivity outside.
  224.             return -1;
  225.         }
  226.         make_root(u);
  227.         access(v);
  228.         // after this, v is root of aux tree that corresponds to path u..v
  229.         return t[v].aand;
  230.     }
  231. };
  232. map <int,vector<int>> adj;
  233. void solve() {
  234.     int n,b;
  235.     cin>>n>>b;
  236.     vector <int> xs;
  237.     map <int,int> v;
  238.     map <int,int> fav;
  239.     vector <int> alls;
  240.     map <int,int> id;
  241.     for (int i=1;i<=n;i++) {
  242.         int x,f;
  243.         cin>>x>>f;
  244.         xs.push_back(x);
  245.         alls.push_back(x);
  246.         fav[x]=f;
  247.         adj[f].push_back(x);
  248.         adj[x].push_back(f);
  249.         int k;
  250.         cin>>k;
  251.         int val=0;
  252.         while (k--) {
  253.             int u;
  254.             cin>>u;
  255.             val|=(1<<u);
  256.         }
  257.         v[x]=val;
  258.     }
  259.     int q;
  260.     cin>>q;
  261.     vector <pair<pair<int,int>,int>> qu(q);
  262.     for (int i=0;i<q;i++) {
  263.         int type;
  264.         cin>>type;
  265.         int x;
  266.         cin>>x;
  267.         alls.push_back(x);
  268.         qu[i].first.first=type;
  269.         qu[i].first.second=x;
  270.         if (type==0) continue;
  271.         if (type==1) {
  272.             int y;
  273.             cin>>y;
  274.             qu[i].second=y;
  275.             continue;
  276.         }
  277.         int f;
  278.         cin>>f;
  279.         fav[x]=f;
  280.         adj[f].push_back(x);
  281.         adj[x].push_back(f);
  282.         int k;
  283.         cin>>k;
  284.         int val=0;
  285.         while (k--) {
  286.             int u;
  287.             cin>>u;
  288.             val|=(1<<u);
  289.         }
  290.         v[x]=val;
  291.         qu[i].second=f;
  292.     }
  293.     sort(alls.begin(),alls.end());
  294.     alls.erase(unique(alls.begin(),alls.end()),alls.end());
  295.     for (int i=0;i<alls.size();i++) {
  296.         id[alls[i]]=i+1;
  297.     }
  298.     vector <int> vals(alls.size()+1);
  299.     vector <int> dead(alls.size()+1,1);
  300.     for (auto i : xs) dead[id[i]]=0;
  301.     for (int i=1;i<=alls.size();i++) vals[i]=v[alls[i-1]];
  302.     LinkCutAND lct(vals.size(),vals);
  303.     for (auto i : xs) {
  304.         if (!dead[id[fav[i]]]) lct.link(id[i],id[fav[i]]);
  305.     }
  306.     for (int i=0;i<q;i++) {
  307.         int type=qu[i].first.first;
  308.         int x=qu[i].first.second;
  309.         int y=qu[i].second;
  310.         if (type==0) {
  311.             dead[id[x]]=1;
  312.             for (auto f : adj[x]) if (!dead[id[f]]) lct.cut(id[x],id[f]);
  313.         } else if (type==1) {
  314.             int res=lct.query_and(id[x],id[y]);
  315.             if (res==-1) cout<<res<<'\n';
  316.             else cout<<__builtin_popcount(res)<<'\n';
  317.         } else {
  318.             dead[id[x]]=0;
  319.             if (!dead[id[y]]) lct.link(id[x],id[y]);
  320.         }
  321.     }
  322. }
  323.  
  324.  
  325. int main() {
  326.     ios::sync_with_stdio(false);
  327.     cin.tie(nullptr);
  328.     int t=1;
  329.     //cin>>t;
  330.     while (t--) solve();
  331.     return 0;
  332. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
1
2
10
42
11
stdout
copy 
Standard output is empty
https://ideone.com/B0QkBr
language:
C++ (gcc 8.3)
created:
2 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!