fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ull = unsigned long long;
  5. const ull INF64 = std::numeric_limits<ull>::max();
  6.  
  7. struct Change {
  8.     int kind;
  9.     int v;
  10.     int delta;
  11. };
  12. struct DSU {
  13.     int n;
  14.     vector<int> parent, sz;
  15.     vector<ull> xorPar;
  16.     vector<vector<ull>> basis;
  17.     vector<Change> hist;
  18.  
  19.     DSU(int N): n(N),
  20.                 parent(N+1), sz(N+1,1),
  21.                 xorPar(N+1,0), basis(N+1)
  22.     { iota(parent.begin(), parent.end(), 0); }
  23.  
  24.     pair<int, ull> find(int v) {
  25.         ull x = 0;
  26.         int u = v;
  27.         while (parent[u] != u) {
  28.             x ^= xorPar[u];
  29.             u  = parent[u];
  30.         }
  31.         return {u, x};
  32.     }
  33.  
  34.     void add_basis(int root, ull x) {
  35.         ull y = x;
  36.         for (ull b : basis[root]) y = min(y, y ^ b);
  37.         if (y == 0) return;
  38.         basis[root].push_back(y);
  39.         hist.push_back({2, root, 0});
  40.     }
  41.  
  42.     void unite(int a, int b, ull w) {
  43.         auto fa = find(a), fb = find(b);
  44.         int ra = fa.first, rb = fb.first;
  45.         ull xa = fa.second, xb = fb.second;
  46.         ull cyc = xa ^ xb ^ w;
  47.  
  48.         if (ra == rb) { add_basis(ra, cyc); return; }
  49.  
  50.         if (sz[ra] < sz[rb]) swap(ra, rb);
  51.         hist.push_back({0, rb, 0});
  52.         parent[rb] = ra;
  53.         xorPar[rb] = cyc;
  54.  
  55.         hist.push_back({1, ra, sz[rb]});
  56.         sz[ra] += sz[rb];
  57.  
  58.         for (ull v : basis[rb]) add_basis(ra, v);
  59.     }
  60.  
  61.     void rollback(size_t checkpoint) {
  62.         while (hist.size() > checkpoint) {
  63.             Change c = hist.back(); hist.pop_back();
  64.             if (c.kind == 2)      basis[c.v].pop_back();
  65.             else if (c.kind == 1) sz[c.v] -= c.delta;
  66.             else {
  67.                 int v = c.v;
  68.                 parent[v] = v;
  69.                 xorPar[v] = 0;
  70.             }
  71.         }
  72.     }
  73. };
  74.  
  75. struct Edge {
  76.     int u, v;
  77.     ull w;
  78.     int red;
  79.     int l, r;
  80. };
  81. struct SegTree {
  82.     int Q;
  83.     vector<vector<Edge>> bucket;
  84.     SegTree(int _Q): Q(_Q), bucket(4*_Q+4) {}
  85.     void add(int node,int L,int R,int ql,int qr,const Edge& e){
  86.         if (qr < L || R < ql) return;
  87.         if (ql <= L && R <= qr){ bucket[node].push_back(e); return; }
  88.         int mid=(L+R)>>1;
  89.         add(node<<1, L, mid, ql, qr, e);
  90.         add(node<<1|1, mid+1, R, ql, qr, e);
  91.     }
  92. };
  93.  
  94. ull reduce_with_basis(const vector<ull>& B, ull x){
  95.     ull ans = x;
  96.     for (ull b: B) ans = min(ans, ans ^ b);
  97.     return ans;
  98. }
  99.  
  100. struct Op {
  101.     int type;
  102.     int u, v, p;
  103. };
  104.  
  105. int main(){
  106.     ios::sync_with_stdio(false);
  107.     cin.tie(nullptr);
  108.  
  109.     int N, M0, Q;
  110.     if(!(cin >> N >> M0 >> Q)) return 0;
  111.  
  112.     const int OFF = N;
  113.     auto id = [&](int v,int par){ return v + par*OFF; };
  114.  
  115.     vector<Edge> intervals; intervals.reserve(M0 + Q);
  116.  
  117.     for (int i=0;i<M0;++i){
  118.         int u,v,c; ull w; cin >> u >> v >> w >> c;
  119.         intervals.push_back({u,v,w,(c==0), 1, Q});
  120.     }
  121.  
  122.     struct InsertData{ int u,v,red,time; ull w; };
  123.     unordered_map<int,InsertData> active; active.reserve(Q*2);
  124.     int nextId = 1;
  125.  
  126.     vector<Op> ops(Q+1);
  127.  
  128.     for(int t=1;t<=Q;++t){
  129.         int tp; cin >> tp;
  130.         if(tp==1){
  131.             int u,v,p; cin >> u >> v >> p;
  132.             ops[t] = {1,u,v,p};
  133.         }else if(tp==2){
  134.             int u,v,c; ull w; cin >> u >> v >> w >> c;
  135.             active[nextId] = {u,v,(c==0),t,w};
  136.             ops[t] = {2,0,0,0};
  137.             ++nextId;
  138.         }else{
  139.             int idd; cin >> idd;
  140.             auto it = active.find(idd);
  141.             auto d  = it->second; active.erase(it);
  142.             intervals.push_back({d.u,d.v,d.w,d.red, d.time, t-1});
  143.             ops[t] = {3,0,0,0};
  144.         }
  145.     }
  146.     for(auto &kv: active){
  147.         auto &d = kv.second;
  148.         intervals.push_back({d.u,d.v,d.w,d.red, d.time, Q});
  149.     }
  150.  
  151.     SegTree seg(Q);
  152.     for(const Edge& e: intervals)
  153.         if(e.l<=e.r) seg.add(1,1,Q,e.l,e.r,e);
  154.  
  155.     DSU dsu(2*N);
  156.     vector<ull> answers; answers.reserve(Q);
  157.  
  158.     function<void(int,int,int)> dfs = [&](int node,int L,int R){
  159.         size_t cp = dsu.hist.size();
  160.         for(const Edge& e : seg.bucket[node]){
  161.             int r = e.red;
  162.             dsu.unite(id(e.u,0), id(e.v,r), e.w);
  163.             dsu.unite(id(e.u,1), id(e.v,r^1), e.w);
  164.         }
  165.  
  166.         if(L==R){
  167.             const Op& op = ops[L];
  168.             if(op.type==1){
  169.                 int u0 = id(op.u,0);
  170.                 int vp = id(op.v,op.p);
  171.  
  172.                 auto fu = dsu.find(u0);
  173.                 auto fv = dsu.find(vp);
  174.  
  175.                 ull raw = fu.second ^ fv.second;
  176.                 ull ans = reduce_with_basis(dsu.basis[fu.first], raw);
  177.                 answers.push_back(ans);
  178.             }
  179.         }else{
  180.             int mid=(L+R)>>1;
  181.             dfs(node<<1, L, mid);
  182.             dfs(node<<1|1, mid+1, R);
  183.         }
  184.         dsu.rollback(cp);
  185.     };
  186.     dfs(1,1,Q);
  187.  
  188.     for(ull x: answers) cout << x << '\n';
  189.     return 0;
  190. }
  191.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
4 3 7
1 2 1 0
2 3 2 1
3 4 3 0
1 1 4 0
2 1 3 4 1
1 1 4 1
2 2 4 5 0
1 1 4 0
3 2
1 1 4 0
stdout 
0
7
0
0
https://ideone.com/2Qcp05
language:
C++14 (gcc 8.3)
created:
3 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!