oj.uz

Submission #447615

# Submission time Handle Problem Language Result Execution time Memory
447615 2021-07-27T06:46:12 Z Esquire Klasika (COCI20_klasika) C++17
0 / 110
 230 ms 524292 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 230 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 230 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 222 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 230 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -