oj.uz

Submission #447626

# Submission time Handle Problem Language Result Execution time Memory
447626 2021-07-27T07:00:49 Z Esquire Klasika (COCI20_klasika) C++17
33 / 110
 1018 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 * 40][2] ,newint ,a[MAXN] ,b[MAXN] ,dist[MAXN] ,tme ,idx[MAXN] ;  
vector <pii> G[MAXN] ; 
set <int> s[MAXN * 40] ; 
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 = 30; 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 = 30; 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 226 ms 449736 KB Output is correct
2 Correct 225 ms 449660 KB Output is correct
3 Correct 224 ms 449736 KB Output is correct
4 Correct 234 ms 449880 KB Output is correct
5 Correct 224 ms 449604 KB Output is correct
6 Correct 227 ms 449748 KB Output is correct
7 Correct 223 ms 449812 KB Output is correct
8 Correct 225 ms 449944 KB Output is correct
9 Correct 219 ms 449604 KB Output is correct
10 Correct 224 ms 449788 KB Output is correct
11 Correct 225 ms 449840 KB Output is correct
12 Correct 225 ms 449864 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 449736 KB Output is correct
2 Correct 225 ms 449660 KB Output is correct
3 Correct 224 ms 449736 KB Output is correct
4 Correct 234 ms 449880 KB Output is correct
5 Correct 224 ms 449604 KB Output is correct
6 Correct 227 ms 449748 KB Output is correct
7 Correct 223 ms 449812 KB Output is correct
8 Correct 225 ms 449944 KB Output is correct
9 Correct 219 ms 449604 KB Output is correct
10 Correct 224 ms 449788 KB Output is correct
11 Correct 225 ms 449840 KB Output is correct
12 Correct 225 ms 449864 KB Output is correct
13 Correct 228 ms 450416 KB Output is correct
14 Correct 226 ms 450908 KB Output is correct
15 Correct 235 ms 451524 KB Output is correct
16 Correct 231 ms 452172 KB Output is correct
17 Correct 224 ms 450252 KB Output is correct
18 Correct 226 ms 450848 KB Output is correct
19 Correct 225 ms 451396 KB Output is correct
20 Correct 228 ms 452032 KB Output is correct
21 Correct 228 ms 450244 KB Output is correct
22 Correct 226 ms 450804 KB Output is correct
23 Correct 226 ms 451476 KB Output is correct
24 Correct 226 ms 452036 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1018 ms 515248 KB Output is correct
2 Runtime error 735 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 449736 KB Output is correct
2 Correct 225 ms 449660 KB Output is correct
3 Correct 224 ms 449736 KB Output is correct
4 Correct 234 ms 449880 KB Output is correct
5 Correct 224 ms 449604 KB Output is correct
6 Correct 227 ms 449748 KB Output is correct
7 Correct 223 ms 449812 KB Output is correct
8 Correct 225 ms 449944 KB Output is correct
9 Correct 219 ms 449604 KB Output is correct
10 Correct 224 ms 449788 KB Output is correct
11 Correct 225 ms 449840 KB Output is correct
12 Correct 225 ms 449864 KB Output is correct
13 Correct 228 ms 450416 KB Output is correct
14 Correct 226 ms 450908 KB Output is correct
15 Correct 235 ms 451524 KB Output is correct
16 Correct 231 ms 452172 KB Output is correct
17 Correct 224 ms 450252 KB Output is correct
18 Correct 226 ms 450848 KB Output is correct
19 Correct 225 ms 451396 KB Output is correct
20 Correct 228 ms 452032 KB Output is correct
21 Correct 228 ms 450244 KB Output is correct
22 Correct 226 ms 450804 KB Output is correct
23 Correct 226 ms 451476 KB Output is correct
24 Correct 226 ms 452036 KB Output is correct
25 Correct 1018 ms 515248 KB Output is correct
26 Runtime error 735 ms 524292 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -