Submission #1116384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116384		8pete8	Klasika (COCI20_klasika)	C++17	110 / 110	2694 ms	190508 KiB

klasika

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
#define double long double
const int mxn=2e5+5,lg=30,inf=1e9,minf=-1e9;
int n,q;
vector<pair<int,pii>>qry;
vector<pii>adj[mxn+10];
int tin[mxn+10],tout[mxn+10],T=0,dist[mxn+10];
void dfs(int cur,int p){
	tin[cur]=++T;
	for(auto i:adj[cur])if(i.f!=p){
		dist[i.f]=dist[cur]^i.s;
		dfs(i.f,cur);
	}
	tout[cur]=T;
}
struct mst{
	set<int>v[2*mxn+10];
	void update(int pos,int val){
		pos+=n;
		v[pos].insert(val);
		for(int i=pos;i>0;i>>=1)v[i>>1].insert(val);
	}
	int check(int pos,int x,int y){
		auto it=v[pos].lb(x);
		if(it==v[pos].end())return 0;
		return (*it)<=y;
	}
	int qry(int l,int r,int x,int y){
		int have=0;
		for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
			if(l&1)have|=check(l++,x,y);
			if(!(r&1))have|=check(r--,x,y);
			if(have)return have;
		}
		return have;
	}
}t;
int32_t main(){
	fastio
	cin>>q;
	n=1;
	for(int i=0;i<q;i++){
		string a;cin>>a;
		int x,y;cin>>x>>y;
		if(a[0]=='A'){
			n++;
			qry.pb({1,{n,y}});
			adj[n].pb({x,y});
			adj[x].pb({n,y});
		}
		else qry.pb({0,{x,y}});
	}
	dfs(1,-1);
	t.update(1,0);
	for(int i=0;i<q;i++){
		if(qry[i].f)t.update(tin[qry[i].s.f],dist[qry[i].s.f]);
		else{
			int cur=0;
			for(int k=30;k>=0;k--){
				if(!(dist[qry[i].s.f]&(1LL<<k))){
					//trying to get 1
					cur+=(1LL<<k);
					if(!t.qry(tin[qry[i].s.s],tout[qry[i].s.s],cur,cur+(1LL<<k)-1))cur-=(1LL<<k);
				}
				else{
					if(!t.qry(tin[qry[i].s.s],tout[qry[i].s.s],cur,cur+(1LL<<k)-1))cur+=(1LL<<k);
				}
			}
			cout<<(dist[qry[i].s.f]^cur)<<'\n';
		}
	}
}
/*
basically given a value x
find a value y in rang [l,r] where x^y is maximum

try fixing bit
let say we fix suffix(most sig bit) to be XXX1001
and the X are not fix
the min value is 0001001 and max value is 1111001
to see if there exist a value with this suffix 
just check if theres a value between 0001001 and 1111001
merge sort tree on euler tour?
each update = log^2(n)
qry =log^3(n)
x=add,y=qry
y=2e5-x;
xlog^2(x) + ylog^2(x)30
xlog^2(x)+(2e5-x)log^2(x)30
worst case x=33,300 y=1e8
should pass??
*/

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