Submission #236657

#	Time	Username	Problem	Language	Result	Execution time	Memory
236657		caoash	Klasika (COCI20_klasika)	C++14	110 / 110	3374 ms	223060 KiB

klasika

#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'
 
struct node{
	int s,e,m;
	set<int> val;
	
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		val.insert(1<<30);
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,int j){
		val.insert(j);
		if (s==e) return;
		else if (i<=m) l->update(i,j);
		else r->update(i,j);
	}
	
	int query(int i,int j,int k){
		if (s==i && e==j){
			int curr=0;
			for (int x=29;~x;x--){
				if (k&(1<<x)){
					//can we find something with 0 bit
					if ((*val.lower_bound(curr))>=curr+(1<<x)) curr^=(1<<x);
				}
				else{
					//1-bit is better
					if ((*val.lower_bound(curr+(1<<x)))<curr+(2<<x)) curr^=(1<<x);
				}
			}
			return curr^k;
		}
		else if (j<=m) return l->query(i,j,k);
		else if (m<i) return r->query(i,j,k);
		else return max(l->query(i,m,k),r->query(m+1,j,k));
	}
}*root=new node(0,200005);
 
struct Q{
	char t;
	int a,b;
	
	Q (char _t,int _a,int _b){
		t=_t,a=_a,b=_b;
	}
};
 
int n;
vector<int> al[200005];
int val[200005];
int in[200005];
int out[200005];
 
int DFS_TIME=0;
void dfs(int i,int p){
	in[i]=++DFS_TIME;
	for (auto &it:al[i]){
		if (it==p) continue;
		
		dfs(it,i);
	}
	out[i]=DFS_TIME;
}
 
vector<Q> queries;
 
inline void read(int& x) {
    x = 0;
    char ch = getchar_unlocked();
    while (ch&16){ //this will break when ‘\n’ or ‘ ‘ is encountered
		x = (x << 3) + (x << 1) + (ch&15);
		ch = getchar_unlocked();
	}
}
 
inline void read(char& x) {
	x=getchar_unlocked();
    char ch = getchar_unlocked();
    while (ch&64) ch=getchar_unlocked();
}
 
 
 
int main(){	
	ios::sync_with_stdio(0);
	cout.tie(0);
	
	read(n);
	
	char s;
	int a,b;
	for (int x=0;x<n;x++){
		read(s),read(a),read(b);
		queries.push_back(Q(s,a,b));
	}
	
	int index=2;
	for (auto &it:queries){
		if (it.t=='A'){
			al[it.a].push_back(index);
			al[index].push_back(it.a);
			
			val[index]=val[it.a]^it.b;
			index++;
		}
	}
	
	dfs(1,-1);
	
	//for (int x=1;x<index;x++) cout<<val[x]<<" "<<in[x]<<" "<<out[x]<<endl;
	root->update(in[1],val[1]); //oof
 
	index=2;
	for (auto &it:queries){
		if (it.t=='A'){
			//cout<<in[index]<<" "<<val[index]<<endl;
			root->update(in[index],val[index]);
			index++;
		}
		else{
			//cout<<in[it.b]<<" "<<out[it.b]<<" "<<val[it.a]<<endl;
			if (it.b!=1) cout<<root->query(in[it.b],out[it.b],val[it.a])<<endl;
			else cout<<root->query(0,200005,val[it.a])<<endl;
		}
	}
}

Compilation message (stderr)

klasika.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("Ofast")
 
klasika.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
klasika.cpp:4:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
klasika.cpp: In constructor 'node::node(int, int)':
klasika.cpp:21:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   s=_s,e=_e,m=s+e>>1;
               ~^~

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