oj.uz

Submission #447623

# Submission time Handle Problem Language Result Execution time Memory
447623 2021-07-27T06:53:33 Z Esquire Klasika (COCI20_klasika) C++17
33 / 110
 1681 ms 524292 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 * 30][2] ,newint ,a[MAXN] ,b[MAXN] ,dist[MAXN] ,tme ,idx[MAXN] ;  
vector <pii> G[MAXN] ; 
set <int> s[MAXN * 30] ; 
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 171 ms 340068 KB Output is correct
2 Correct 189 ms 340112 KB Output is correct
3 Correct 171 ms 340160 KB Output is correct
4 Correct 170 ms 340240 KB Output is correct
5 Correct 174 ms 340116 KB Output is correct
6 Correct 172 ms 340192 KB Output is correct
7 Correct 174 ms 340340 KB Output is correct
8 Correct 169 ms 340292 KB Output is correct
9 Correct 170 ms 340164 KB Output is correct
10 Correct 172 ms 340184 KB Output is correct
11 Correct 170 ms 340248 KB Output is correct
12 Correct 167 ms 340352 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 340068 KB Output is correct
2 Correct 189 ms 340112 KB Output is correct
3 Correct 171 ms 340160 KB Output is correct
4 Correct 170 ms 340240 KB Output is correct
5 Correct 174 ms 340116 KB Output is correct
6 Correct 172 ms 340192 KB Output is correct
7 Correct 174 ms 340340 KB Output is correct
8 Correct 169 ms 340292 KB Output is correct
9 Correct 170 ms 340164 KB Output is correct
10 Correct 172 ms 340184 KB Output is correct
11 Correct 170 ms 340248 KB Output is correct
12 Correct 167 ms 340352 KB Output is correct
13 Correct 180 ms 340848 KB Output is correct
14 Correct 172 ms 341300 KB Output is correct
15 Correct 172 ms 342052 KB Output is correct
16 Correct 185 ms 342596 KB Output is correct
17 Correct 175 ms 340808 KB Output is correct
18 Correct 175 ms 341208 KB Output is correct
19 Correct 181 ms 341960 KB Output is correct
20 Correct 186 ms 342596 KB Output is correct
21 Correct 177 ms 340616 KB Output is correct
22 Correct 174 ms 341276 KB Output is correct
23 Correct 181 ms 341952 KB Output is correct
24 Correct 177 ms 342532 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 944 ms 407472 KB Output is correct
2 Correct 1562 ms 474236 KB Output is correct
3 Runtime error 1681 ms 524292 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 340068 KB Output is correct
2 Correct 189 ms 340112 KB Output is correct
3 Correct 171 ms 340160 KB Output is correct
4 Correct 170 ms 340240 KB Output is correct
5 Correct 174 ms 340116 KB Output is correct
6 Correct 172 ms 340192 KB Output is correct
7 Correct 174 ms 340340 KB Output is correct
8 Correct 169 ms 340292 KB Output is correct
9 Correct 170 ms 340164 KB Output is correct
10 Correct 172 ms 340184 KB Output is correct
11 Correct 170 ms 340248 KB Output is correct
12 Correct 167 ms 340352 KB Output is correct
13 Correct 180 ms 340848 KB Output is correct
14 Correct 172 ms 341300 KB Output is correct
15 Correct 172 ms 342052 KB Output is correct
16 Correct 185 ms 342596 KB Output is correct
17 Correct 175 ms 340808 KB Output is correct
18 Correct 175 ms 341208 KB Output is correct
19 Correct 181 ms 341960 KB Output is correct
20 Correct 186 ms 342596 KB Output is correct
21 Correct 177 ms 340616 KB Output is correct
22 Correct 174 ms 341276 KB Output is correct
23 Correct 181 ms 341952 KB Output is correct
24 Correct 177 ms 342532 KB Output is correct
25 Correct 944 ms 407472 KB Output is correct
26 Correct 1562 ms 474236 KB Output is correct
27 Runtime error 1681 ms 524292 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -