Submission #257194

#	Time	Username	Problem	Language	Result	Execution time	Memory
257194		blacktulip	Klasika (COCI20_klasika)	C++17	110 / 110	3783 ms	524288 KiB

klasika

//~ #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define int long long
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 200002;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t,say=1,nodee=1,visit[li*30][5],xorr[li],l[li],r[li],x[li],y[li],q;
int cev;
char s[li][10];
//~ set<int> st[li];
vector<int> v,vec[li],vect;
vector<set<int>> st;

inline void build_trie(int xxx){
	int node=1;
	//~ cout<<xxx<<"*(*(*(\n";
	for(int i=0;i<(int)v.size();i++){
		auto it=st[node].lower_bound(l[xxx]);
		int yess=0;
		if(it!=st[node].end()){
			if(*it<=r[xxx])yess=1;
		}
		if(yess==0)st[node].insert(l[xxx]);
		if(visit[node][v[i]])node=visit[node][v[i]];
		else{
			st.resize(nodee+2);
			visit[node][v[i]]=++nodee;
			node=nodee;
		}
	}
	auto it=st[node].lower_bound(l[xxx]);
	int yess=0;
	if(it!=st[node].end()){
		if(*it<=r[xxx])yess=1;
	}
	if(yess==0)st[node].insert(l[xxx]);
}

inline void ask_trie(int xx){
	int node=1;
	//~ cout<<l[xx]<<" : :  : "<<r[xx]<<endl;
	for(int i=0;i<(int)v.size();i++){
		auto it=st[visit[node][!v[i]]].lower_bound(l[xx]);
		//~ if(xx==3 && node==1)cout<<node<<"****"<<endl;
		//~ if(visit[node][!v[i]]){
		int yess=0;
			//~ cout<<*it<<endl;
			if(it!=st[visit[node][!v[i]]].end()){
				//~ if(xx==3)cout<<*it<<endl;
				
				if(visit[node][!v[i]] && *it<=r[xx]){node=visit[node][!v[i]];vect.pb(1);yess=1;}
			}
		//~ }
		if(yess==0 && visit[node][v[i]]){node=visit[node][v[i]];vect.pb(0);}
	}
}

inline void dfs(int node,int ata){
	l[node]=++q;
	r[node]=q;
	for(int i=0;i<(int)vec[node].size();i++){
		int go=vec[node][i];
		if(go==ata)continue;
		dfs(go,node);
		r[node]=max(r[node],r[go]);
	}
}

main(void){
	//~ freopen("at.txt","r",stdin);
	//~ freopen("att.txt","w",stdout);
	scanf("%lld",&t);
	//~ set.resize();
	for(int i=1;i<=t;i++){
		//~ int x,y;
		scanf("%s %lld %lld",s[i],&x[i],&y[i]);
		if(s[i][0]=='A'){
			//~ xorr[++say]=(xorr[x[i]]^y[i]);
			vec[x[i]].pb(++say);
			vec[say].pb(x[i]);
			//~ v.clear();
			//~ while(at){
				//~ v.pb(at%2);
				//~ at/=2;
			//~ }
			//~ while((int)v.size()<35)v.pb(0);
			//~ reverse(v.begin(),v.end());
			//~ build_trie();
			//~ continue;
		}
		//~ int at=xorr[x];
		//~ v.clear();
		//~ while(at){
			//~ v.pb(at%2);
			//~ at/=2;
		//~ }
		//~ while((int)v.size()<35)v.pb(0);
		//~ reverse(v.begin(),v.end());
		//~ vect.clear();
		//~ ask_trie();
		//~ reverse(vect.begin(),vect.end());
		//~ int ans=0;
		//~ for(int i=0;i<(int)vect.size();i++){
			//~ if(vect[i]==1)ans=(ans^(1ll<<i));
		//~ }
		//~ printf("%lld\n",ans);
	}
	st.resize(2);
	dfs(1,0);
	//~ st.resize(say*30);
	for(int i=1;i<=30;i++)v.pb(0);
	build_trie(1);
	
	
	//~ cout<<l[5]<<" : : "<<r[5]<<" : : "<<xorr[]endl;
	say=1;
	for(int i=1;i<=t;i++){
		if(s[i][0]=='A'){
			xorr[++say]=(xorr[x[i]]^y[i]);
			//~ vec[x[i]].pb(say);
			int at=xorr[say];
			//~ vec[say].pb(x[i]);
			v.clear();
			while(at){
				v.pb(at%2);
				at/=2;
			}
			while((int)v.size()<30)v.pb(0);
			reverse(v.begin(),v.end());
			build_trie(say);
			continue;
		}
		int at=xorr[x[i]];
		v.clear();
		while(at){
			v.pb(at%2);
			at/=2;
		}
		while((int)v.size()<30)v.pb(0);
		reverse(v.begin(),v.end());
		vect.clear();
		ask_trie(y[i]);
		reverse(vect.begin(),vect.end());
		int ans=0;
		for(int j=0;j<(int)vect.size();j++){
			if(vect[j]==1)ans=(ans^(1ll<<j));
		}
		printf("%lld\n",ans);
	}
	//~ cout<<xorr[3]<<endl;
	return 0;
}

Compilation message (stderr)

klasika.cpp:90:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(void){
          ^
klasika.cpp: In function 'int main()':
klasika.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&t);
  ~~~~~^~~~~~~~~~~
klasika.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s %lld %lld",s[i],&x[i],&y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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