oj.uz

Submission #447610

# Submission time Handle Problem Language Result Execution time Memory
447610 2021-07-27T06:43:36 Z Esquire Klasika (COCI20_klasika) C++17
33 / 110
 673 ms 218996 KB 
#include<bits/stdc++.h>
using namespace std ; 
typedef long long ll ; 
typedef pair <int ,int> pii ; 
const int MAXN = 5e5 + 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 31 ms 55128 KB Output is correct
2 Correct 30 ms 55232 KB Output is correct
3 Correct 31 ms 55260 KB Output is correct
4 Correct 31 ms 55304 KB Output is correct
5 Correct 30 ms 55168 KB Output is correct
6 Correct 30 ms 55240 KB Output is correct
7 Correct 33 ms 55304 KB Output is correct
8 Correct 31 ms 55384 KB Output is correct
9 Correct 32 ms 55124 KB Output is correct
10 Correct 32 ms 55244 KB Output is correct
11 Correct 33 ms 55328 KB Output is correct
12 Correct 30 ms 55372 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 55128 KB Output is correct
2 Correct 30 ms 55232 KB Output is correct
3 Correct 31 ms 55260 KB Output is correct
4 Correct 31 ms 55304 KB Output is correct
5 Correct 30 ms 55168 KB Output is correct
6 Correct 30 ms 55240 KB Output is correct
7 Correct 33 ms 55304 KB Output is correct
8 Correct 31 ms 55384 KB Output is correct
9 Correct 32 ms 55124 KB Output is correct
10 Correct 32 ms 55244 KB Output is correct
11 Correct 33 ms 55328 KB Output is correct
12 Correct 30 ms 55372 KB Output is correct
13 Correct 32 ms 55764 KB Output is correct
14 Correct 33 ms 56500 KB Output is correct
15 Correct 37 ms 57156 KB Output is correct
16 Correct 38 ms 57656 KB Output is correct
17 Correct 33 ms 55764 KB Output is correct
18 Correct 38 ms 56320 KB Output is correct
19 Correct 37 ms 57036 KB Output is correct
20 Correct 38 ms 57624 KB Output is correct
21 Correct 33 ms 55756 KB Output is correct
22 Correct 35 ms 56316 KB Output is correct
23 Correct 35 ms 57020 KB Output is correct
24 Correct 38 ms 57504 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 673 ms 218996 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 31 ms 55128 KB Output is correct
2 Correct 30 ms 55232 KB Output is correct
3 Correct 31 ms 55260 KB Output is correct
4 Correct 31 ms 55304 KB Output is correct
5 Correct 30 ms 55168 KB Output is correct
6 Correct 30 ms 55240 KB Output is correct
7 Correct 33 ms 55304 KB Output is correct
8 Correct 31 ms 55384 KB Output is correct
9 Correct 32 ms 55124 KB Output is correct
10 Correct 32 ms 55244 KB Output is correct
11 Correct 33 ms 55328 KB Output is correct
12 Correct 30 ms 55372 KB Output is correct
13 Correct 32 ms 55764 KB Output is correct
14 Correct 33 ms 56500 KB Output is correct
15 Correct 37 ms 57156 KB Output is correct
16 Correct 38 ms 57656 KB Output is correct
17 Correct 33 ms 55764 KB Output is correct
18 Correct 38 ms 56320 KB Output is correct
19 Correct 37 ms 57036 KB Output is correct
20 Correct 38 ms 57624 KB Output is correct
21 Correct 33 ms 55756 KB Output is correct
22 Correct 35 ms 56316 KB Output is correct
23 Correct 35 ms 57020 KB Output is correct
24 Correct 38 ms 57504 KB Output is correct
25 Runtime error 673 ms 218996 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -