Submission #201099

#	Time	Username	Problem	Language	Result	Execution time	Memory
201099		mraron	Klasika (COCI20_klasika)	C++14	110 / 110	1396 ms	405496 KiB

klasika

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<chrono>
#include<bitset>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const double PI=3.1415926535897932384626433832795;
const ll INF = 1LL<<62;
const ll MINF = -1LL<<62;

template<typename T> T getint() {
	T val=0;
	char c;
	
	bool neg=false;
	while((c=gc()) && !(c>='0' && c<='9')) {
		neg|=c=='-';
	}

	do {
		val=(val*10)+c-'0';
	} while((c=gc()) && (c>='0' && c<='9'));

	return val*(neg?-1:1);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)


int q;

struct op {
	int typ,a,b;
};

const int MAXN=200001;

int n=1;
vector<op> lst;
vector<pair<int,int>> adj[MAXN];

int sz[MAXN], par[MAXN], d[MAXN];
void dfs_pre(int x) {
	sz[x]=1;
	for(auto i:adj[x]) {
		if(!sz[i.xx]) {
			par[i.xx]=x;
			d[i.xx]=i.yy^d[x];
			dfs_pre(i.xx);
			sz[x]+=sz[i.xx];
		}
	}
}

int hld_top[MAXN], hld_id[MAXN], hld_pos[MAXN], pos=0, id=1;
void dfs_hld(int x) {
//	cerr<<x<<" "<<pos<<"\n";
	hld_id[x]=id;
	hld_pos[x]=pos++;
	if(!hld_top[hld_id[x]]) {
		hld_top[hld_id[x]]=x;
	}
	
	int best=0;
	for(auto i:adj[x]) {
		if(par[x]==i.xx) continue ;
		if(!best || sz[best]<sz[i.xx]) best=i.xx;
	}
	
	if(best>0) dfs_hld(best);
	for(auto i:adj[x]) {
		if(par[x]!=i.xx && i.xx!=best) {
			id++;
			dfs_hld(i.xx);
		}	
	}
}


struct node {
	int sub[2];
	node() {
		sub[0]=sub[1]=0;
	}
} trie[30*8*MAXN];
int nxt=1;

void insert(int root, int num) {
	for(int i=30;i>=0;i--) {
		int c=(num&(1<<i))!=0;
		if(trie[root].sub[c]==0) {
			trie[root].sub[c]=nxt++;
		}
		
		root=trie[root].sub[c];
	}
}

int mx(int root, int with) {
	if(root==0) return 0;
	if(trie[root].sub[0]==0 && trie[root].sub[1]==0) return 0;

	
	int ans=0;
	for(int i=30;i>=0;i--) {
		int c=(with&(1<<i))!=0;
		if(trie[root].sub[1-c]!=0) {
			ans|=1<<i;
			root=trie[root].sub[1-c];
		}else {
			root=trie[root].sub[c];
		}
	}
	
	return ans;
}

int tree[4*MAXN];

void add(int ind, int L, int R, int i, int j, int mit) {
	//cerr<<ind<<" "<<L<<" "<<R<<" "<<i<<" "<<j<<" "<<mit<<"add\n"<<flush;
	if(R<i || j<L) return ;
	if(i<=L && R<=j) {
		if(tree[ind]==0) tree[ind]=nxt++;
		insert(tree[ind], mit);
		return ;
	}
	
	add(2*ind, L, (L+R)/2, i, j, mit);
	add(2*ind+1, (L+R)/2+1, R, i, j, mit);
}

int mx(int ind, int L, int R, int i, int with) {
	//cerr<<ind<<" "<<L<<" "<<R<<" "<<i<<" "<<i<<" "<<with<<"mx\n"<<flush;

	if(R<i || i<L) return 0;
	
	int ans=mx(tree[ind], with);
	if(L!=R) ans=max(ans, max(mx(2*ind, L, (L+R)/2, i, with), mx(2*ind+1, (L+R)/2+1, R, i, with)));
	
	return ans;
}

void add(int root, int dd) {
	while(root>0) {
		int blk=hld_id[root];
		int tp=hld_top[blk];
		add(1,0,pos-1,hld_pos[tp],hld_pos[root],dd);
		root=par[tp];
	}
}

int query(int a, int b) {
	int base=d[a];
	//cerr<<base<<"\n";
	//cerr<<hld_pos[b]<<"\n";
	return mx(1,0,pos-1,hld_pos[b],base);
}

int main() {
	IO;
	cin>>q;
	lst.resize(q);
	for(int i=0;i<q;++i) {
		string t;
		cin>>t;
		lst[i].typ=(t=="Add"?0:1);
		cin>>lst[i].a>>lst[i].b;
		
		if(lst[i].typ==0) {
			adj[lst[i].a].push_back({n+1, lst[i].b});
			adj[n+1].push_back({lst[i].a, lst[i].b});
			lst[i].a=n+1;
			
			n++;
		}
	}
	
	dfs_pre(1);
	dfs_hld(1);
	
	add(1,0,pos-1,0,0,0);
	for(auto i:lst) {
		if(i.typ==0) {
			//cerr<<"typ0\n";
			add(i.a, d[i.a]);
		}else {
			//cerr<<"typ1\n";
			cout<<query(i.a,i.b)<<"\n";
		}
	}
	
	return 0;
}

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