Submission #1276009

#TimeUsernameProblemLanguageResultExecution timeMemory
1276009papauloKlasika (COCI20_klasika)C++20
0 / 110
271 ms76376 KiB
#include <bits/stdc++.h> using namespace std; #define MAXQ 200200 vector<int> trie[MAXQ][2]; vector<int> mn[MAXQ]; int id[MAXQ]; vector<int> chi[MAXQ]; int t=1; int val[MAXQ]; vector<pair<int, pair<int, int>>> qs[MAXQ]; int ans[MAXQ]; int sz[MAXQ]; void dfsadd(int t1, int t2, int v1, int v2) { for(int i=0;i<2;i++) { if(trie[t1][i][v1]) { int t=trie[t2][i][v2]; if(!t) { t=trie[t2][i].size(); trie[t2][i][v2]=t; mn[t2].push_back(2e9); trie[t2][0].push_back(0); trie[t2][1].push_back(0); } mn[t2][t]=min(mn[t2][t], mn[t1][v1]); dfsadd(t1, t2, trie[t1][i][v1], t); } } } void insert(int t, int v, int tmp) { int n=0; for(int i=31;i>=0;i--) { int c=(v>>i)&1; int nxt=trie[t][c][n]; if(!nxt) { nxt=trie[t][c].size(); trie[t][c][n]=nxt; mn[t].push_back(2e9); trie[t][0].push_back(0); trie[t][1].push_back(0); } mn[t][nxt]=min(mn[t][nxt], tmp); n=nxt; } } int search(int t, int v, int tmp) { int n=0; int ans=0; for(int i=31;i>=0;i--) { int c=(v>>i)&1; int nxt=trie[t][c^1][n]; if(nxt&&mn[t][nxt]<=tmp) { ans|=1<<i; } else nxt=trie[t][c][n]; n=nxt; } return ans; } void dfs1(int v) { sz[v]=1; for(auto u : chi[v]) { dfs1(u); sz[v]+=sz[u]; } } void dfs2(int v) { int bst=0; for(auto u : chi[v]) { if(sz[u]>sz[bst]) bst=u; } if(!bst) { id[v]=v; mn[v].push_back(v); trie[v][0].push_back(0); trie[v][1].push_back(0); } else { dfs2(bst); id[v]=id[bst]; } for(auto u : chi[v]) { if(u==bst) continue; dfs2(u); dfsadd(id[u], id[v], 0, 0); for(int i=0;i<2;i++) trie[id[u]][i].clear(); } insert(id[v], val[v], v); for(auto pr : qs[v]) { int i=pr.first, vl=pr.second.first, t=pr.second.second; ans[i]=search(id[v], vl, t); } } int main() { memset(ans, 0xff, sizeof(ans)); cin.tie(nullptr); ios::sync_with_stdio(false); val[1]=0; int q; cin >> q; for(int i=0;i<q;i++) { string op; cin >> op; if(op=="Add") { int x, y; cin >> x >> y; ++t; chi[x].push_back(t); val[t]=val[x]^y; } else { int a, b; cin >> a >> b; qs[b].push_back({i, {val[a], t}}); } } sz[0]=0; dfs1(1); dfs2(1); for(int i=0;i<q;i++) { int a=ans[i]; if(a>=0) cout << a << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...