oj.uz

Submission #447609

# Submission time Handle Problem Language Result Execution time Memory
447609 2021-07-27T06:42:37 Z Esquire Klasika (COCI20_klasika) C++17
33 / 110
 239 ms 94836 KB 
#include<bits/stdc++.h>
using namespace std ; 
typedef long long ll ; 
typedef pair <int ,int> pii ; 
const int MAXN = 2e5 + 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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 22348 KB Output is correct
2 Correct 13 ms 22372 KB Output is correct
3 Correct 15 ms 22348 KB Output is correct
4 Correct 13 ms 22476 KB Output is correct
5 Correct 14 ms 22312 KB Output is correct
6 Correct 14 ms 22376 KB Output is correct
7 Correct 14 ms 22368 KB Output is correct
8 Correct 14 ms 22500 KB Output is correct
9 Correct 13 ms 22220 KB Output is correct
10 Correct 13 ms 22344 KB Output is correct
11 Correct 13 ms 22372 KB Output is correct
12 Correct 13 ms 22476 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 22348 KB Output is correct
2 Correct 13 ms 22372 KB Output is correct
3 Correct 15 ms 22348 KB Output is correct
4 Correct 13 ms 22476 KB Output is correct
5 Correct 14 ms 22312 KB Output is correct
6 Correct 14 ms 22376 KB Output is correct
7 Correct 14 ms 22368 KB Output is correct
8 Correct 14 ms 22500 KB Output is correct
9 Correct 13 ms 22220 KB Output is correct
10 Correct 13 ms 22344 KB Output is correct
11 Correct 13 ms 22372 KB Output is correct
12 Correct 13 ms 22476 KB Output is correct
13 Correct 16 ms 22896 KB Output is correct
14 Correct 18 ms 23596 KB Output is correct
15 Correct 19 ms 24192 KB Output is correct
16 Correct 21 ms 24812 KB Output is correct
17 Correct 16 ms 22860 KB Output is correct
18 Correct 18 ms 23536 KB Output is correct
19 Correct 20 ms 24088 KB Output is correct
20 Correct 22 ms 24708 KB Output is correct
21 Correct 17 ms 22956 KB Output is correct
22 Correct 23 ms 23500 KB Output is correct
23 Correct 24 ms 24140 KB Output is correct
24 Correct 21 ms 24780 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 239 ms 94836 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 22348 KB Output is correct
2 Correct 13 ms 22372 KB Output is correct
3 Correct 15 ms 22348 KB Output is correct
4 Correct 13 ms 22476 KB Output is correct
5 Correct 14 ms 22312 KB Output is correct
6 Correct 14 ms 22376 KB Output is correct
7 Correct 14 ms 22368 KB Output is correct
8 Correct 14 ms 22500 KB Output is correct
9 Correct 13 ms 22220 KB Output is correct
10 Correct 13 ms 22344 KB Output is correct
11 Correct 13 ms 22372 KB Output is correct
12 Correct 13 ms 22476 KB Output is correct
13 Correct 16 ms 22896 KB Output is correct
14 Correct 18 ms 23596 KB Output is correct
15 Correct 19 ms 24192 KB Output is correct
16 Correct 21 ms 24812 KB Output is correct
17 Correct 16 ms 22860 KB Output is correct
18 Correct 18 ms 23536 KB Output is correct
19 Correct 20 ms 24088 KB Output is correct
20 Correct 22 ms 24708 KB Output is correct
21 Correct 17 ms 22956 KB Output is correct
22 Correct 23 ms 23500 KB Output is correct
23 Correct 24 ms 24140 KB Output is correct
24 Correct 21 ms 24780 KB Output is correct
25 Runtime error 239 ms 94836 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -