Submission #1181229

#TimeUsernameProblemLanguageResultExecution timeMemory
1181229tdkhaiKlasika (COCI20_klasika)C++17
33 / 110
5093 ms33128 KiB
/* _.-- ,.--. .' .' / @ |'..--------._ / \._/ '. / .-.- \ ( / \ \ \\ '. | # \\ \ -. / :\ | )._____.' \ " | / \ | \ ) | |./' :__ \.-' '--' */ #include<bits/stdc++.h> #define ll long long #define llll pair<int,int> #define ii pair<int,int> #define fi first #define se second #define FOR(i,l,r) for(int i=l;i<=r;i++) #define FOD(i,r,l) for(int i=r;i>=l;i--) #define ull unsigned long long #define iii pair<int,pii> #define iv pair<pii,pii> #define db double #define ld long double #define pb push_back using namespace std; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, -1, 1}; const int dxx[] = {1, 1, -1, -1, 2, 2, -2, -2}; const int dyy[] = {2, -2, 2, -2, 1, -1, 1, -1}; const ll INF=1e18; struct node { node *a[2]; set<int> s; node() { a[0]=a[1]=NULL; s.clear(); } }; struct quanque { bool asked; int x,y; }; const int N=2e5+5; vector<quanque>Query; int l[N],r[N],n,timer,sx[N],ans[N],cc; vector<ii> a[N]; void dfs(int u=1,int cur=0) { l[u]=++timer; sx[u]=cur; for(int i=0;i<a[u].size();i++) { int v=a[u][i].fi,xo=a[u][i].se; dfs(v,cur^xo); } r[u]=timer; } void update(int pos,int v,node *p) { // cout << ":: " << v << "::" << ' '; for(int i=30;i>=0;i--) { int bit=((v>>i)&1); if(p->a[bit]==NULL) { p->a[bit]=new node(); } // cout << bit << ' '; p=p->a[bit]; p->s.insert(pos); } } int get(int u,int v,int val,node *p) { int ret=0; for(int i=30;i>=0;i--) { int bit=((val>>i)&1); if(p->a[1-bit]==NULL or (lower_bound(p->a[1-bit]->s.begin(),p->a[1-bit]->s.end(),u)==upper_bound(p->a[1-bit]->s.begin(),p->a[1-bit]->s.end(),v))) { // if(p->a[1-bit]==NULL) cout << "cond1:"; // else cout << "cond2:"; // cout << bit << ' '; p=p->a[bit]; } else { // cout << "+" << 1-bit << ' '; ret+=1<<i; p=p->a[1-bit]; } } return ret; } void solve() { cin >> n; node *root=new node(); int cnt=1; for(int i=1;i<=n;i++) { string type; int x,y; cin >> type >> x >> y; if(type=="Add") { cnt++; a[x].push_back({cnt,y}); Query.push_back({0,cnt,-1}); } else { Query.pb({1,x,y}); } } dfs(); // for(int i=1;i<=cnt;i++) // { // cout << sx[i] << " \n"[i==cnt]; // } update(1,0,root); // cout << '\n'; for(quanque q:Query) { if(q.asked) { // cout << sx[q.x] << '\n'; ans[++cc]=get(l[q.y],r[q.y],sx[q.x],root); } else { // cout << q.x << '\n'; update(l[q.x],sx[q.x],root); // cout << '\n'; } } for(int i=1;i<=cc;i++) { cout << ans[i] << '\n'; } } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); // freopen("tdk.inp","r",stdin); // freopen("tdk.out","w",stdout); int t=1; //cin >> t; while(t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...