oj.uz

답안 #498986

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
498986 2021-12-26T22:31:52 Z inksamurai Klasika (COCI20_klasika) C++17
0 / 110
 2165 ms 130924 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define crep(i,x,n) for(ll i=x;i<n;i++)
#define drep(i,n) for(ll 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<ll,ll,ll>;
using pii=pair<ll,ll>;
using vi=vector<ll>;
using vll=vector<long long>;

int main(){
_3qplfh5;
	ll q;
	cin>>q;
	vec(tupiii) qry;
	ll n=1;
	rep(_,q){
		string s;
		cin>>s;
		ll t=0;
		if(s=="Add"){
			t=1;
			n++;
		}
		ll _a,_b;
		cin>>_a>>_b;
		qry.pb({t,_a,_b});
	}
	vec(vec(pii)) adj(n);
	ll 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);
	ll tm=0;
	auto dfs=[&](auto self,ll v,ll par)->void{
		tin[v]=tm++;
		tour.pb(v);
		for(auto edge : adj[v]){
			ll 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,set<ll>>) rbts(32);
	now=1;
	for(auto [t,_a,_b] : qry){
		if(t==0){
			_a--,_b--;
			ll k=psum[_a];
			ll need=0;
			drep(j,31){
				if(!(k&(1ll<<j))){
					need|=(1ll<<j);
				}
				bool pokita=0;
				if(rbts[j].find(need)!=rbts[j].end()){
					auto it=rbts[j][need].lower_bound(tin[_b]);
					if(it!=rbts[j][need].end() and *it<tout[_b]){
						pokita=1;
					}
				}
				if(not pokita){
					need^=(1ll<<j);
				}
			}
			cout<<(need^k)<<"\n";
		}else{
			ll v=now;
			ll wata=0;
			drep(j,31){
				if(psum[v]&(1ll<<j)) wata|=(1ll<<j);
				rbts[j][wata].insert(tin[v]);
			}
			// cout<<psum[v]<<"\n";
			now++;
		}
	}
//	
	return 0;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Incorrect 1 ms 588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Incorrect 1 ms 588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2165 ms 130924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Incorrect 1 ms 588 KB Output isn't correct
3 Halted 0 ms 0 KB -