oj.uz

Submission #198074

# Submission time Handle Problem Language Result Execution time Memory
198074 2020-01-24T15:40:12 Z AryaKnight Klasika (COCI20_klasika) C++14
110 / 110
 4437 ms 464956 KB 
#include<bits/stdc++.h>
using namespace std;

#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define ll long long
#define vi vector<int>
#define pi pair<int,int>
#define mp make_pair
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int mod=1e9+7;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int mul(int a,int b)
{
	return ((a)*1ll*(b))%mod;
}
 
void add(int &a,int b)
{
	a+=b;
	if(a>=mod)a-=mod;
}
 
int sub(int a,int b){
	a-=b;
	if(a<0){
		a+=mod;
	}
	return a;
}
 
int powz(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1){
			res=mul(res,a);
		}
		b/=2;
		a=mul(a,a);
	}
	return res;
}
 
template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x) {
	input>>x.F>>x.S;
	return input;
}
 
template <typename A>
istream& operator>>(istream& input,vector<A>& x) {
	for(auto& i:x)
		input>>i;
	return input;
}
 
template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {
	for(auto& i:x)
		output<<i<<' ';
	return output;
}
 
const int N=200005,N2=1000000;

struct Node{
	Node *zero,*one;
	set<int>st;
	Node(){
		zero=one=NULL;
	}
	Node(Node *left,Node *right){
		zero=left;
		right=one;
	}
};

void trie_add(Node *node,int val,int ind,int bits=30){
	node->st.insert(ind);
	if(bits==-1){
		return;
	}
	if(val&(1ll<<bits)){
		if(node->one==NULL){
			node->one=new Node();
		}
		trie_add(node->one,val,ind,bits-1);
	}
	else{
		if(node->zero==NULL){
			node->zero=new Node();
		}
		trie_add(node->zero,val,ind,bits-1);
	}
}

int trie_query(Node *node,int val,int fst,int lst,int bits=30){
	if(bits==-1){
		return 0;
	}
	if(val&(1ll<<bits)){
		if(node->zero==NULL){
			return trie_query(node->one,val,fst,lst,bits-1);
		}			
		auto it=node->zero->st.lower_bound(fst);
		if(it==node->zero->st.end()||(*it)>=lst){
			return trie_query(node->one,val,fst,lst,bits-1);
		}
		else{
			return (1ll<<bits)+trie_query(node->zero,val,fst,lst,bits-1);
		}
	}
	else{
		if(node->one==NULL){
			return trie_query(node->zero,val,fst,lst,bits-1);
		}
		auto it=node->one->st.lower_bound(fst);
		if(it==node->one->st.end()||(*it)>=lst){
			return trie_query(node->zero,val,fst,lst,bits-1);
		}
		else{
			return (1ll<<bits)+trie_query(node->one,val,fst,lst,bits-1);
		}
	}
}

vector<int>adj[N];
int in[N],out[N],tt=0,prec[N];
map<pi,int>xr;

void dfs(int u,int p,int val=0){
	in[u]=tt++;
	prec[u]=val;
	for(auto i:adj[u]){
		if(i!=p){
			dfs(i,u,xr[{i,u}]^val);
		}
	}
	out[u]=tt;
}

void solve(){
	int q;
	cin>>q;
	int n=0;
	vector<pi>queries(q);
	vector<bool>add(q);
	for(int i=0;i<q;i++){
		string s;
		cin>>s;
		if(s[0]=='A'){
			int x,y;
			cin>>x>>y;
			x--;
			adj[x].pb(++n);
			xr[{x,n}]=y;
			xr[{n,x}]=y;
			queries[i]={n,-1};
			adj[n].pb(x);
			add[i]=true;
		}
		else{
			int x,y;
			cin>>x>>y;
			x--;y--;
			queries[i]={x,y};
		}
	}
	Node root;
	trie_add(&root,0,0);
	dfs(0,-1,0);
	for(int i=0;i<q;i++){
		if(add[i]){
			trie_add(&root,prec[queries[i].F],in[queries[i].F]);
		}
		else{
			cout<<trie_query(&root,prec[queries[i].F],in[queries[i].S],out[queries[i].S])<<"\n";
		}
	}
	
}
 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int tc=1;
	//~cin>>tc;
	for(int _=0;_<tc;_++){
		//~ cout<<"Case #"<<_+1<<": ";
		solve();
		if(_!=tc-1)
		cout<<"\n";
	}
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 7 ms 5496 KB Output is correct
4 Correct 7 ms 5624 KB Output is correct
5 Correct 6 ms 5240 KB Output is correct
6 Correct 7 ms 5368 KB Output is correct
7 Correct 7 ms 5496 KB Output is correct
8 Correct 7 ms 5624 KB Output is correct
9 Correct 7 ms 5240 KB Output is correct
10 Correct 7 ms 5368 KB Output is correct
11 Correct 7 ms 5500 KB Output is correct
12 Correct 7 ms 5624 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 7 ms 5496 KB Output is correct
4 Correct 7 ms 5624 KB Output is correct
5 Correct 6 ms 5240 KB Output is correct
6 Correct 7 ms 5368 KB Output is correct
7 Correct 7 ms 5496 KB Output is correct
8 Correct 7 ms 5624 KB Output is correct
9 Correct 7 ms 5240 KB Output is correct
10 Correct 7 ms 5368 KB Output is correct
11 Correct 7 ms 5500 KB Output is correct
12 Correct 7 ms 5624 KB Output is correct
13 Correct 11 ms 6520 KB Output is correct
14 Correct 13 ms 7928 KB Output is correct
15 Correct 17 ms 9336 KB Output is correct
16 Correct 21 ms 10488 KB Output is correct
17 Correct 12 ms 6456 KB Output is correct
18 Correct 14 ms 7800 KB Output is correct
19 Correct 17 ms 9080 KB Output is correct
20 Correct 20 ms 10260 KB Output is correct
21 Correct 11 ms 6520 KB Output is correct
22 Correct 16 ms 7928 KB Output is correct
23 Correct 19 ms 9208 KB Output is correct
24 Correct 20 ms 10360 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 987 ms 128752 KB Output is correct
2 Correct 1715 ms 243344 KB Output is correct
3 Correct 2664 ms 353708 KB Output is correct
4 Correct 3292 ms 464560 KB Output is correct
5 Correct 1153 ms 124644 KB Output is correct
6 Correct 2063 ms 235468 KB Output is correct
7 Correct 3011 ms 341712 KB Output is correct
8 Correct 3876 ms 447964 KB Output is correct
9 Correct 994 ms 124576 KB Output is correct
10 Correct 1779 ms 236872 KB Output is correct
11 Correct 2586 ms 344948 KB Output is correct
12 Correct 3411 ms 451196 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 7 ms 5368 KB Output is correct
3 Correct 7 ms 5496 KB Output is correct
4 Correct 7 ms 5624 KB Output is correct
5 Correct 6 ms 5240 KB Output is correct
6 Correct 7 ms 5368 KB Output is correct
7 Correct 7 ms 5496 KB Output is correct
8 Correct 7 ms 5624 KB Output is correct
9 Correct 7 ms 5240 KB Output is correct
10 Correct 7 ms 5368 KB Output is correct
11 Correct 7 ms 5500 KB Output is correct
12 Correct 7 ms 5624 KB Output is correct
13 Correct 11 ms 6520 KB Output is correct
14 Correct 13 ms 7928 KB Output is correct
15 Correct 17 ms 9336 KB Output is correct
16 Correct 21 ms 10488 KB Output is correct
17 Correct 12 ms 6456 KB Output is correct
18 Correct 14 ms 7800 KB Output is correct
19 Correct 17 ms 9080 KB Output is correct
20 Correct 20 ms 10260 KB Output is correct
21 Correct 11 ms 6520 KB Output is correct
22 Correct 16 ms 7928 KB Output is correct
23 Correct 19 ms 9208 KB Output is correct
24 Correct 20 ms 10360 KB Output is correct
25 Correct 987 ms 128752 KB Output is correct
26 Correct 1715 ms 243344 KB Output is correct
27 Correct 2664 ms 353708 KB Output is correct
28 Correct 3292 ms 464560 KB Output is correct
29 Correct 1153 ms 124644 KB Output is correct
30 Correct 2063 ms 235468 KB Output is correct
31 Correct 3011 ms 341712 KB Output is correct
32 Correct 3876 ms 447964 KB Output is correct
33 Correct 994 ms 124576 KB Output is correct
34 Correct 1779 ms 236872 KB Output is correct
35 Correct 2586 ms 344948 KB Output is correct
36 Correct 3411 ms 451196 KB Output is correct
37 Correct 1914 ms 129316 KB Output is correct
38 Correct 2653 ms 243016 KB Output is correct
39 Correct 3214 ms 356280 KB Output is correct
40 Correct 3753 ms 464956 KB Output is correct
41 Correct 2097 ms 124700 KB Output is correct
42 Correct 2969 ms 234872 KB Output is correct
43 Correct 3799 ms 341596 KB Output is correct
44 Correct 4437 ms 447100 KB Output is correct
45 Correct 2115 ms 124364 KB Output is correct
46 Correct 2942 ms 236372 KB Output is correct
47 Correct 3619 ms 343216 KB Output is correct
48 Correct 4056 ms 450956 KB Output is correct