oj.uz

Submission #224252

# Submission time Handle Problem Language Result Execution time Memory
224252 2020-04-17T15:16:00 Z jamielim Klasika (COCI20_klasika) C++14
33 / 110
 2907 ms 441540 KB 
#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.upper_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.upper_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

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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5248 KB Output is correct
2 Correct 8 ms 5248 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Incorrect 7 ms 5120 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5248 KB Output is correct
2 Correct 8 ms 5248 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Incorrect 7 ms 5120 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1043 ms 125316 KB Output is correct
2 Correct 1537 ms 233488 KB Output is correct
3 Correct 1995 ms 337188 KB Output is correct
4 Correct 2680 ms 441540 KB Output is correct
5 Correct 892 ms 123384 KB Output is correct
6 Correct 1436 ms 229628 KB Output is correct
7 Correct 1991 ms 331348 KB Output is correct
8 Correct 2907 ms 433272 KB Output is correct
9 Correct 1038 ms 123000 KB Output is correct
10 Correct 1555 ms 230440 KB Output is correct
11 Correct 1991 ms 333560 KB Output is correct
12 Correct 2609 ms 435192 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5248 KB Output is correct
2 Correct 8 ms 5248 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Incorrect 7 ms 5120 KB Output isn't correct
6 Halted 0 ms 0 KB -