Submission #1110368

#TimeUsernameProblemLanguageResultExecution timeMemory
1110368FucKanhKlasika (COCI20_klasika)C++14
110 / 110
1779 ms293960 KiB
#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define p3i pair<int,pii> #define p4i pair<pii,pii> #define fi first #define se second using namespace std; const int maxn = 2e5 + 2; int h[maxn],ans[maxn]; vector<p3i> a[maxn]; vector<p4i> qr[maxn]; struct node { int u,pa,jump,len,vpa,vjump; node() {}; node(int u) : u(u) {} node(int u, int pa, int jump, int len, int vpa,int vjump) : u(u), pa(pa), jump(jump), len(len), vpa(vpa), vjump(vjump) {} }; node info[maxn]; void add(int u,int pa,int w) { h[u] = h[pa] + 1; int len,jump,vpa = w,vjump; if (info[pa].len == info[info[pa].jump].len) { len = info[pa].len * 2 + 1; jump = info[info[pa].jump].jump; vjump = w ^ info[pa].vjump ^ info[info[pa].jump].vjump; } else { len = 1; jump = pa; vjump = w; } info[u] = node(u,pa,jump,len,vpa,vjump); } pii binlift(int u, int k) { int des = h[u] - k; int value = 0; while (h[u] != des) { // cerr << u << " " << h[u] << " " << des << endl; // system("pause"); if (h[info[u].jump] < des) { value ^= info[u].vpa; u = info[u].pa; } else { value ^= info[u].vjump; u = info[u].jump; } } return {u,value}; } int LCA(int u, int v) { if (h[u] > h[v]) swap(u,v); pii tmp = binlift(v,h[v]-h[u]); int val = 0; v = tmp.first; // cerr << u << " " << v << endl; while (u != v) { if (info[u].jump != info[v].jump) { val ^= info[u].vjump ^ info[v].vjump; u = info[u].jump; v = info[v].jump; } else { val ^= info[u].vpa ^ info[v].vpa; u = info[u].pa; v = info[v].pa; } } // cerr << val << " " << tmp.second << endl; return val ^ tmp.second; } struct nodetrie { int la, t[2]; nodetrie *p[2]; nodetrie() { t[0] = t[1] = 0; p[0] = p[1] = nullptr; la = 0; } nodetrie(nodetrie *l, nodetrie *r, int tl, int tr) { t[0] = (tl); t[1] = (tr); p[0] = (l); p[1] = (r); la = 0; } }; void push(nodetrie *p,int pos) { if (p->la) { for (int i = 0; i < 2; i++) { if (p->p[i]!=nullptr) p->p[i]->la ^= p->la; } if (p->la & (1<<pos-1)) { swap(p->p[0],p->p[1]), swap(p->t[0],p->t[1]); } p->la=0; } } class trie { public: int sz; nodetrie *root = new nodetrie(); void update(nodetrie *p, int pos, int val, int t) { if (pos==0) return; push(p,pos); int bit = (val&(1<<pos-1))!=0; if (p->p[bit]==nullptr){ p->t[bit] = t; p->p[bit] = new nodetrie(); } else { p->t[bit] = min(t,p->t[bit]); } update( p->p[bit], pos - 1, val, t); } int get(nodetrie *p, int pos, int val, int t) { if (pos==0) return 0; assert(p!=nullptr); push(p,pos); int bit = (val&(1<<pos-1))!=0; if (p->p[bit]==nullptr || p->t[bit] > t){ return get(p->p[!bit],pos-1,val,t) | (!bit << pos-1); } else { return get(p->p[bit],pos-1,val,t) | (bit << pos-1); } } int get(int val, int t) { return get(root,31,val,t); } void update(int val, int t) { update(root,31,val,t); sz++; } void addlazy(int val) { root->la ^= val; } void init(int t) { update(root,31,0,t); sz = 1; } void print(nodetrie *p, int pos, int val, int t) { push(p,pos); if (pos==0) { cerr << ">> " << val << " "<< t<< endl; return; } for (int i = 0; i < 2; i++) { if (p->p[i] == nullptr) continue; print(p->p[i], pos-1, val | (i<<pos-1), max(t,p->t[i])); } } void print(int u) { cerr << "tree print: " << u << " sz: " << sz << endl; print(root,31,0,0); } void del(nodetrie *p, int pos) { if (pos==0) { delete p; return; } for (int i = 0; i < 2; i++) { if (p->p[i]!=nullptr) del(p->p[i],pos-1); } delete p; } }; void merged(nodetrie *a, nodetrie *b, int pos, int &sz) { if (pos==0) return; push(a,pos); push(b,pos); for (int i = 0; i < 2; i++) { if (b->p[i] == nullptr) continue; if (a->p[i] == nullptr) { a->p[i] = new nodetrie(); a->t[i] = b->t[i]; if (pos-1==0) sz++; } else { a->t[i] = min(a->t[i], b->t[i]); } merged(a->p[i], b->p[i], pos - 1,sz); } } trie tree[maxn]; void dfs(int u) { // cerr <<"vst u:" << u << endl; if (a[u].empty()) { // tree[u].print(u); for (p4i val : qr[u]) { int x,y,idx,t; tie(x,y) = val.fi; tie(idx,t) = val.se; int ori = LCA(x,y); // cerr << "ori: " << ori << endl; ans[idx] = ori ^ tree[u].get(~ori,t); } return; } for (p3i tmp : a[u]) { int w,v; w = tmp.se.fi; v = tmp.fi; tree[v].init(tmp.se.se); dfs(v); tree[v].addlazy(w); if (tree[u].sz < tree[v].sz) swap(tree[u], tree[v]); merged(tree[u].root, tree[v].root, 31,tree[u].sz); tree[v].del(tree[v].root,31); } // tree[u].print(u); for (p4i val : qr[u]) { int x,y,idx,t; tie(x,y) = val.fi; tie(idx,t) = val.se; int ori = LCA(x,y); // cerr << ori << " : " << t << endl; ans[idx] = ori ^ tree[u].get(~ori,t); } } void solve() { int q; cin >> q; int cnt = 1, cntqr=0, t = 0; info[1] = node(1,0,0,-1,0,0); for (int i = 1; i <= q; i++) { string s;cin >> s; t++; if (s=="Add") { int x,w; cin >> x >> w; add(++cnt,x,w); a[x].push_back({cnt,{w,t}}); } else { int x,y; cin >> x >> y; qr[y].push_back({{x,y},{++cntqr,t}}); } } tree[1].init(0); dfs(1); for (int i = 1; i <= cntqr; i++) { cout << ans[i] << '\n'; } } void file(string name) { if (fopen((name + ".inp").c_str(), "r")) { freopen((name + ".inp").c_str(), "r", stdin); freopen((name + ".out").c_str(), "w", stdout); } } signed main() { file("TaskKlasika"); cin.tie(0) -> sync_with_stdio(0); solve(); return 0; }

Compilation message (stderr)

klasika.cpp: In function 'void push(nodetrie*, int)':
klasika.cpp:104:28: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  104 |         if (p->la & (1<<pos-1)) {
      |                         ~~~^~
klasika.cpp: In member function 'void trie::update(nodetrie*, int, int, int)':
klasika.cpp:118:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  118 |         int bit = (val&(1<<pos-1))!=0;
      |                            ~~~^~
klasika.cpp: In member function 'int trie::get(nodetrie*, int, int, int)':
klasika.cpp:133:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  133 |         int bit = (val&(1<<pos-1))!=0;
      |                            ~~~^~
klasika.cpp:135:62: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  135 |             return get(p->p[!bit],pos-1,val,t) | (!bit << pos-1);
      |                                                           ~~~^~
klasika.cpp:138:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  138 |             return get(p->p[bit],pos-1,val,t) | (bit << pos-1);
      |                                                         ~~~^~
klasika.cpp: In member function 'void trie::print(nodetrie*, int, int, int)':
klasika.cpp:167:48: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  167 |             print(p->p[i], pos-1, val | (i<<pos-1), max(t,p->t[i]));
      |                                             ~~~^~
klasika.cpp: In function 'void file(std::string)':
klasika.cpp:266:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  266 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:267:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  267 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...