제출 #1276014

#제출 시각아이디문제언어결과실행 시간메모리
1276014papauloKlasika (COCI20_klasika)C++20
110 / 110
647 ms315684 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]; vector<pair<int, int>> vec[MAXQ]; int ans[MAXQ]; int sz[MAXQ]; 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); for(auto pr : vec[id[u]]) { insert(id[v], pr.second, pr.first); vec[id[v]].push_back(pr); } for(int i=0;i<2;i++) trie[id[u]][i].clear(); vec[id[u]].clear(); } vec[id[v]].push_back({v, val[v]}); 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...