Submission #447615

#	Time	Username	Problem	Language	Result	Execution time	Memory
447615		Esquire	Klasika (COCI20_klasika)	C++17	0 / 110	230 ms	524292 KiB

klasika

#include<bits/stdc++.h>
using namespace std ; 
typedef long long ll ; 
typedef pair <int ,int> pii ; 
const int MAXN = 6e6 + 5; 
const int MOD = 1e9 + 7 ; 

#define F first 
#define S second 
#define debug(x) cerr << #x << " :" << x << "\n" 

int q ,n ,st[MAXN] ,ed[MAXN] ,child[MAXN][2] ,newint ,a[MAXN] ,b[MAXN] ,dist[MAXN] ,tme ,idx[MAXN] ;  
vector <pii> G[MAXN] ; 
set <int> s[MAXN] ; 
string sq[MAXN] ; 

void dfs(int u){
	st[u] = tme++ ; 
	for (auto [v ,w] : G[u]){
		dist[v] = dist[u] ^ w ; 
		dfs(v) ; 
	}
	ed[u] = tme++ ; 
}

void add(int p ,int id){
	int root = 0 ; 
	for (int i = 31; i >= 0; i--){
		int x = (p >> i) & 1 ;
		if (child[root][x] == -1){
			child[root][x] = ++newint ; 
		}
		root = child[root][x] ; 
		s[root].insert(st[id]) ;
	}
}

bool check(int id ,int v){
	auto it = s[id].lower_bound(st[v]) ; 
	if (it == s[id].end()){
		return false ; 
	}
	return (*it) <= ed[v] ; 
}

void ans(int u ,int v){ 
	int len = dist[u] ; 
	int root = 0 ; 
	for (int i = 31; i >= 0; i--){
		int x = (len >> i) & 1 ; 
		if (child[root][1 - x] != -1 && check(child[root][1 - x] ,v)){
			root = child[root][1 - x] ; 
			if (!x){
				len += (1 << i) ; 
			}
		}
		else {
			if (x == 1){
				len -= (1 << i) ; 
			}
			root = child[root][x] ; 
		}
	}
	cout << len << "\n" ; 
}

int main (){
	ios::sync_with_stdio(false); cin.tie(0) ;cout.tie(0) ; 
	memset(child ,-1 ,sizeof child) ; 
	cin >> q ; 
	n = 1 ;
	for (int i = 1; i <= q; i++){
		cin >> sq[i] >> a[i] >> b[i] ; 
		if (sq[i][0] == 'A'){
			n++ ; 
			G[a[i]].push_back({n ,b[i]}) ; 
			idx[i] = n ; 
		}
	}
	dfs(1) ;
	add(dist[1] ,1) ; 
	for (int i = 1; i <= q; i++){
		if (sq[i][0] == 'Q'){
			ans(a[i] ,b[i]) ; 
		}
		else {
			add(dist[idx[i]] ,idx[i]) ;
		}
	}
	return 0 ; 
}



 

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