Submission #224254

#	Time	Username	Problem	Language	Result	Execution time	Memory
224254		jamielim	Klasika (COCI20_klasika)	C++14	110 / 110	3142 ms	441896 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
const int MAXN=200005;
const int BITS=30;
int n=1,q,ctr=1;
pair<int,pair<int,int> > query[MAXN];
vector<pair<int,int> > adj[MAXN];
int l[MAXN],r[MAXN],x[MAXN]; //discovery, finish, xor from root

struct trie{
	set<int> s;
	trie *z,*o;
	trie(){z=o=NULL;}
	void add(int h,int v,int idx){ //h: height, number of bits; v: value at subtree root; idx: discovery index being added
		s.insert(idx);
		if(h<0)return;
		if(v&(1<<h)){
			if(o==NULL)o=new trie();
			o->add(h-1,v,idx);
		}else{
			if(z==NULL)z=new trie();
			z->add(h-1,v,idx);
		}
	}
	int get(int h,int v,int fr,int to){ //h: height, number of bits; v: value of query node; [fr,to): range allowed
		if(h<0)return 0;
		if((v&(1<<h))==0){ //want 1
			if(o==NULL||o->s.lower_bound(fr)==o->s.lower_bound(to))return z->get(h-1,v,fr,to);
			return (1<<h)+o->get(h-1,v,fr,to);
		}else{ //want 0
			if(z==NULL||z->s.lower_bound(fr)==z->s.lower_bound(to))return o->get(h-1,v,fr,to);
			return (1<<h)+z->get(h-1,v,fr,to);
		}
	}
}*root=new trie();

void dfs(int u,int p,int v){
	l[u]=ctr++;
	x[u]=v;
	for(int i=0;i<(int)adj[u].size();i++){
		if(adj[u][i].first==p)continue;
		dfs(adj[u][i].first,u,v^adj[u][i].second);
	}
	r[u]=ctr;
}

int main(){
	scanf("%d",&q);
	char op[10];int a,b;
	for(int i=0;i<q;i++){
		scanf("%s%d%d",op,&a,&b);
		if(op[0]=='A'){
			n++;
			query[i]=mp(0,mp(a,b));
			adj[n].push_back(mp(a,b));
			adj[a].push_back(mp(n,b));
		}else{
			query[i]=mp(1,mp(a,b));
		}
	}
	dfs(1,0,0);
	root->add(BITS,0,l[1]);
	int nn=1;
	for(int i=0;i<q;i++){
		if(query[i].first==0){
			nn++;
			root->add(BITS,x[nn],l[nn]);
		}else{
			printf("%d\n",root->get(BITS,x[query[i].second.first],l[query[i].second.second],r[query[i].second.second]));
		}
	}
}

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
klasika.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d%d",op,&a,&b);
   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44