oj.uz

Submission #498992

# Submission time Handle Problem Language Result Execution time Memory
498992 2021-12-27T00:17:52 Z inksamurai Klasika (COCI20_klasika) C++17
33 / 110
 2456 ms 280060 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3qplfh5 ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using tupiii=tuple<int,int,int>;
using pii=pair<int,int>;
using vi=vector<int>;
using vll=vector<long long>;
 
int main(){
_3qplfh5;
	int q;
	cin>>q;
	vec(tupiii) qry;
	int n=1;
	rep(_,q){
		string s;
		cin>>s;
		int t=0;
		if(s=="Add"){
			t=1;
			n++;
		}
		int _a,_b;
		cin>>_a>>_b;
		qry.pb({t,_a,_b});
	}
	vec(vec(pii)) adj(n);
	int now=1;
	for(auto [t,_a,_b] : qry){
		if(t==1){
			adj[_a-1].pb({now,_b});
			adj[now].pb({_a-1,_b});
			now++;
		}
	}
	//rabbit tour
	vi tour;
	vi tin(n,0),tout(n,0);
	vi psum(n,0);
	int tm=0;
	auto dfs=[&](auto self,int v,int par)->void{
		tin[v]=tm++;
		tour.pb(v);
		for(auto edge : adj[v]){
			int u=edge.fi;
			if(u!=par){
				psum[u]=psum[v]^edge.se;
				// cout<<edge.se<<"\n";
				self(self,u,v);
			}
		}
		tout[v]=tm++;
		tour.pb(v);
	};
	dfs(dfs,0,-1);
	vec(std::map<ll,vi>) rbts(32);
	rep(j,31){
		rbts[j][0].pb(tin[0]);
	}
	now=1;
	for(auto [t,_a,_b] : qry){
		if(t==0){
			_a--,_b--;
			int k=psum[_a];
			int need=0;
			int ans=0;
			drep(j,31){
				if(!(k&(1<<j))){
					need|=(1<<j);
				}
				bool pokita=0;
				if(rbts[j].find(need)!=rbts[j].end()){
					auto it=lower_bound(all(rbts[j][need]),tin[_b]);
					if(it!=rbts[j][need].end() and *it<tout[_b]){
						pokita=1;
					}
				}
				if(not pokita){
					if(!(k&(1<<j))) need^=(1<<j);
					else need|=(1<<j);
				}
			}
			ans=need^k;
			cout<<ans<<"\n";
		}else{
			int v=now;
			int wata=0;
			drep(j,31){
				if(psum[v]&(1<<j)) wata|=(1<<j);
				rbts[j][wata].pb(tin[v]);
			}
			now++;
		}
	}
//	
	return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Incorrect 1 ms 332 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 1614 ms 81708 KB Output is correct
2 Correct 1954 ms 150996 KB Output is correct
3 Correct 2225 ms 214316 KB Output is correct
4 Correct 2430 ms 280060 KB Output is correct
5 Correct 1527 ms 82564 KB Output is correct
6 Correct 1897 ms 149912 KB Output is correct
7 Correct 2263 ms 211576 KB Output is correct
8 Correct 2456 ms 275004 KB Output is correct
9 Correct 1572 ms 82364 KB Output is correct
10 Correct 1960 ms 150800 KB Output is correct
11 Correct 2261 ms 213204 KB Output is correct
12 Correct 2456 ms 276684 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -