oj.uz

Submission #499292

# Submission time Handle Problem Language Result Execution time Memory
499292 2021-12-27T20:12:39 Z inksamurai Klasika (COCI20_klasika) C++17
110 / 110
 2844 ms 475812 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3qplfh5 ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using tupiii=tuple<int,int,int>;
using pii=pair<int,int>;
using vi=vector<int>;
using vll=vector<long long>;

struct node{
	set<int> ids;
	int nxt[2]={-1,-1};
};

int main(){
_3qplfh5;
	int q;
	cin>>q;
	vec(tupiii) qry;
	int n=1;
	rep(_,q){
		string s;
		cin>>s;
		int t=0;
		if(s=="Add"){
			t=1;
			n++;
		}
		int _a,_b;
		cin>>_a>>_b;
		qry.pb({t,_a,_b});
	}
	vec(vec(pii)) adj(n);
	{
		int now=1;
		for(auto [t,_a,_b] : qry){
			if(t==1){
				adj[_a-1].pb({now,_b});
				adj[now].pb({_a-1,_b});
				now++;
			}
		}
	}
	//rabbit tour
	vi tin(n,0),tout(n,0);
	vi psum(n,0);
	{
		int tm=0;
		auto dfs=[&](auto self,int v,int par)->void{
			tin[v]=tm++;
			for(auto edge : adj[v]){
				int u=edge.fi;
				if(u!=par){
					psum[u]=psum[v]^edge.se;
					self(self,u,v);
				}
			}
			tout[v]=tm++;
		};
		dfs(dfs,0,-1);
	}
	vec(node) rbts;
	rbts.pb({});
	auto add=[&](int v,int ai){
		int root=0;
		drep(j,31){
			bool x=ai&(1<<j);
			if(rbts[root].nxt[x]==-1){
				rbts[root].nxt[x]=sz(rbts);
				rbts.pb({});
			}
			root=rbts[root].nxt[x];
			rbts[root].ids.insert(tin[v]);
		}
	};
	auto get=[&](auto self,int root,int i,int ai,int _tin,int _tout)->int{
		if(i<0) return 0;
		bool x=ai&(1<<i);
		int neroot=rbts[root].nxt[x^1];
		if(neroot==-1){
			return self(self,rbts[root].nxt[x],i-1,ai,_tin,_tout);
		}else{
			auto it=rbts[neroot].ids.lower_bound(_tin);
			if(it!=rbts[neroot].ids.end() and *it<_tout){
				return self(self,neroot,i-1,ai,_tin,_tout)+(1<<i);
			}else{
				return self(self,rbts[root].nxt[x],i-1,ai,_tin,_tout);
			}
		}
	};
	int now=0;
	add(0,0);
	for(auto [t,_a,_b] : qry){
		if(t==0){
			_a--,_b--;
			int val=get(get,0,30,psum[_a],tin[_b],tout[_b]);
			cout<<val<<"\n";
		}else{
			now++;
			add(now,psum[now]);
		}
	}
//	
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 700 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 1 ms 436 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 696 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 700 KB Output is correct
12 Correct 1 ms 716 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 700 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 1 ms 436 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 696 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 700 KB Output is correct
12 Correct 1 ms 716 KB Output is correct
13 Correct 4 ms 1768 KB Output is correct
14 Correct 5 ms 3364 KB Output is correct
15 Correct 6 ms 3744 KB Output is correct
16 Correct 8 ms 6432 KB Output is correct
17 Correct 4 ms 1764 KB Output is correct
18 Correct 5 ms 3356 KB Output is correct
19 Correct 6 ms 3616 KB Output is correct
20 Correct 8 ms 4512 KB Output is correct
21 Correct 4 ms 1756 KB Output is correct
22 Correct 6 ms 3352 KB Output is correct
23 Correct 7 ms 3616 KB Output is correct
24 Correct 9 ms 4512 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 116704 KB Output is correct
2 Correct 1278 ms 233256 KB Output is correct
3 Correct 1868 ms 288716 KB Output is correct
4 Correct 2387 ms 475628 KB Output is correct
5 Correct 742 ms 114604 KB Output is correct
6 Correct 1375 ms 229488 KB Output is correct
7 Correct 2008 ms 283604 KB Output is correct
8 Correct 2700 ms 467524 KB Output is correct
9 Correct 735 ms 114984 KB Output is correct
10 Correct 1374 ms 229972 KB Output is correct
11 Correct 1887 ms 285596 KB Output is correct
12 Correct 2398 ms 468828 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 700 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 1 ms 436 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 696 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 700 KB Output is correct
12 Correct 1 ms 716 KB Output is correct
13 Correct 4 ms 1768 KB Output is correct
14 Correct 5 ms 3364 KB Output is correct
15 Correct 6 ms 3744 KB Output is correct
16 Correct 8 ms 6432 KB Output is correct
17 Correct 4 ms 1764 KB Output is correct
18 Correct 5 ms 3356 KB Output is correct
19 Correct 6 ms 3616 KB Output is correct
20 Correct 8 ms 4512 KB Output is correct
21 Correct 4 ms 1756 KB Output is correct
22 Correct 6 ms 3352 KB Output is correct
23 Correct 7 ms 3616 KB Output is correct
24 Correct 9 ms 4512 KB Output is correct
25 Correct 704 ms 116704 KB Output is correct
26 Correct 1278 ms 233256 KB Output is correct
27 Correct 1868 ms 288716 KB Output is correct
28 Correct 2387 ms 475628 KB Output is correct
29 Correct 742 ms 114604 KB Output is correct
30 Correct 1375 ms 229488 KB Output is correct
31 Correct 2008 ms 283604 KB Output is correct
32 Correct 2700 ms 467524 KB Output is correct
33 Correct 735 ms 114984 KB Output is correct
34 Correct 1374 ms 229972 KB Output is correct
35 Correct 1887 ms 285596 KB Output is correct
36 Correct 2398 ms 468828 KB Output is correct
37 Correct 1096 ms 117108 KB Output is correct
38 Correct 1687 ms 233636 KB Output is correct
39 Correct 2100 ms 291112 KB Output is correct
40 Correct 2554 ms 475812 KB Output is correct
41 Correct 1255 ms 115128 KB Output is correct
42 Correct 1868 ms 229684 KB Output is correct
43 Correct 2340 ms 283728 KB Output is correct
44 Correct 2844 ms 467868 KB Output is correct
45 Correct 1281 ms 115536 KB Output is correct
46 Correct 1881 ms 230220 KB Output is correct
47 Correct 2256 ms 284408 KB Output is correct
48 Correct 2642 ms 469020 KB Output is correct