oj.uz

Submission #447634

# Submission time Handle Problem Language Result Execution time Memory
447634 2021-07-27T07:26:26 Z Esquire Klasika (COCI20_klasika) C++17
110 / 110
 2859 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std ; 
typedef long long ll ; 
typedef pair <int ,int> pii ; 
const int MAXN = 4e5 + 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] ,len ,root ,x;  
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){
	root = 0 ; 
	for (int i = 30; i >= 0; i--){
		x = (p >> i) & 1 ;
		if (child[root][x] == -1){
			child[root][x] = ++newint ; 
			s[newint] = new set <int> () ; 
		}
		root = child[root][x] ; 
		(*s[root]).insert(st[id]) ;
	}
}

bool check(int &id ,int &v){
	if ((*s[id]).lower_bound(st[v]) == (*s[id]).end()){
		return false ; 
	}
	return (*(*s[id]).lower_bound(st[v])) <= ed[v] ; 
}

void ans(int &u ,int &v){ 
	len = dist[u] ; 
	root = 0 ; 
	for (int i = 30; i >= 0; i--){
		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 ; 
		}
	}
	int tmp = 1;
	dfs(tmp) ;
	add(dist[1] ,tmp) ; 
	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 53 ms 116292 KB Output is correct
2 Correct 56 ms 116424 KB Output is correct
3 Correct 60 ms 116572 KB Output is correct
4 Correct 57 ms 116596 KB Output is correct
5 Correct 57 ms 116348 KB Output is correct
6 Correct 56 ms 116420 KB Output is correct
7 Correct 61 ms 116540 KB Output is correct
8 Correct 54 ms 116608 KB Output is correct
9 Correct 56 ms 116348 KB Output is correct
10 Correct 55 ms 116448 KB Output is correct
11 Correct 56 ms 116560 KB Output is correct
12 Correct 55 ms 116700 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 116292 KB Output is correct
2 Correct 56 ms 116424 KB Output is correct
3 Correct 60 ms 116572 KB Output is correct
4 Correct 57 ms 116596 KB Output is correct
5 Correct 57 ms 116348 KB Output is correct
6 Correct 56 ms 116420 KB Output is correct
7 Correct 61 ms 116540 KB Output is correct
8 Correct 54 ms 116608 KB Output is correct
9 Correct 56 ms 116348 KB Output is correct
10 Correct 55 ms 116448 KB Output is correct
11 Correct 56 ms 116560 KB Output is correct
12 Correct 55 ms 116700 KB Output is correct
13 Correct 59 ms 117548 KB Output is correct
14 Correct 58 ms 118728 KB Output is correct
15 Correct 61 ms 120008 KB Output is correct
16 Correct 61 ms 120932 KB Output is correct
17 Correct 57 ms 117468 KB Output is correct
18 Correct 61 ms 118608 KB Output is correct
19 Correct 67 ms 119776 KB Output is correct
20 Correct 60 ms 120900 KB Output is correct
21 Correct 59 ms 117424 KB Output is correct
22 Correct 58 ms 118604 KB Output is correct
23 Correct 64 ms 119784 KB Output is correct
24 Correct 62 ms 120848 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 928 ms 226800 KB Output is correct
2 Correct 1500 ms 328240 KB Output is correct
3 Correct 2016 ms 429244 KB Output is correct
4 Correct 2509 ms 524288 KB Output is correct
5 Correct 955 ms 226800 KB Output is correct
6 Correct 1620 ms 326024 KB Output is correct
7 Correct 2056 ms 421028 KB Output is correct
8 Correct 2535 ms 516320 KB Output is correct
9 Correct 936 ms 226604 KB Output is correct
10 Correct 1495 ms 327052 KB Output is correct
11 Correct 2005 ms 423788 KB Output is correct
12 Correct 2512 ms 518876 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 116292 KB Output is correct
2 Correct 56 ms 116424 KB Output is correct
3 Correct 60 ms 116572 KB Output is correct
4 Correct 57 ms 116596 KB Output is correct
5 Correct 57 ms 116348 KB Output is correct
6 Correct 56 ms 116420 KB Output is correct
7 Correct 61 ms 116540 KB Output is correct
8 Correct 54 ms 116608 KB Output is correct
9 Correct 56 ms 116348 KB Output is correct
10 Correct 55 ms 116448 KB Output is correct
11 Correct 56 ms 116560 KB Output is correct
12 Correct 55 ms 116700 KB Output is correct
13 Correct 59 ms 117548 KB Output is correct
14 Correct 58 ms 118728 KB Output is correct
15 Correct 61 ms 120008 KB Output is correct
16 Correct 61 ms 120932 KB Output is correct
17 Correct 57 ms 117468 KB Output is correct
18 Correct 61 ms 118608 KB Output is correct
19 Correct 67 ms 119776 KB Output is correct
20 Correct 60 ms 120900 KB Output is correct
21 Correct 59 ms 117424 KB Output is correct
22 Correct 58 ms 118604 KB Output is correct
23 Correct 64 ms 119784 KB Output is correct
24 Correct 62 ms 120848 KB Output is correct
25 Correct 928 ms 226800 KB Output is correct
26 Correct 1500 ms 328240 KB Output is correct
27 Correct 2016 ms 429244 KB Output is correct
28 Correct 2509 ms 524288 KB Output is correct
29 Correct 955 ms 226800 KB Output is correct
30 Correct 1620 ms 326024 KB Output is correct
31 Correct 2056 ms 421028 KB Output is correct
32 Correct 2535 ms 516320 KB Output is correct
33 Correct 936 ms 226604 KB Output is correct
34 Correct 1495 ms 327052 KB Output is correct
35 Correct 2005 ms 423788 KB Output is correct
36 Correct 2512 ms 518876 KB Output is correct
37 Correct 1698 ms 230660 KB Output is correct
38 Correct 2196 ms 331452 KB Output is correct
39 Correct 2654 ms 431852 KB Output is correct
40 Correct 2801 ms 524288 KB Output is correct
41 Correct 1627 ms 227396 KB Output is correct
42 Correct 2134 ms 326012 KB Output is correct
43 Correct 2460 ms 421188 KB Output is correct
44 Correct 2754 ms 515564 KB Output is correct
45 Correct 1716 ms 227012 KB Output is correct
46 Correct 2327 ms 327152 KB Output is correct
47 Correct 2633 ms 422592 KB Output is correct
48 Correct 2859 ms 518748 KB Output is correct