oj.uz

답안 #446538

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446538 2021-07-22T10:50:12 Z Arinoor Klasika (COCI20_klasika) C++17
66 / 110
 1054 ms 524292 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
const int inf = 1e9 + 10;
const int maxlg = 31;

vector<pair<int, int>> query[maxn];
int ans_query[maxn];
vector<int> G[maxn];
int val[maxn], sz[maxn], adding_time[maxn];

struct Trie{
	struct node{
		node *child[2];
		int mini;

		node(){
			child[0] = nullptr;
			child[1] = nullptr;
			mini = inf;
		}

		node *getChild(bool bit){
			if(child[bit] == nullptr)
				child[bit] = new node();
			return child[bit];
		}

		bool check(bool bit, int ind){
			if(child[bit] == nullptr)
				return false;
			return (child[bit]->mini) < ind;
		}

	};
	
	node *root;

	Trie(){
		root = new node();
	}

	void add(int v){
		node *cur = root;
		for(int i = maxlg - 1; i >= 0; i --){
			cur = cur->getChild(val[v] & (1 << i));
			cur->mini = min(cur->mini, adding_time[v]);
		}
	}

	int get(int a, int ind){
		node *cur = root;
		int ans = 0;
		for(int i = maxlg - 1; i >= 0; i --){
			bool bit = (a & (1 << i));
			if(cur->check(!bit, ind)){
				if(!bit)
					ans += (1 << i);
				cur = cur->child[!bit];
			}
			else{
				if(bit)
					ans += (1 << i);
				cur = cur->child[bit];
			}
		}
		return ans ^ a;
	}

	void Clear(){
		root = new node();
	}

} T;

void dfs_sz(int v){
	sz[v] = 1;
	for(int u : G[v]){
		dfs_sz(u);
		sz[v] += sz[u];
	}
}

void dfs_add(int v){
	T.add(v);
	for(int u : G[v])
		dfs_add(u);
}

void dsu(int v, bool keep){
	int big_child = -1;
	int maxi = 0;
	for(int u : G[v]){
		if(sz[u] > maxi){
			maxi = sz[u];
			big_child = u;
		}
	}
	if(big_child == -1){
		for(auto q : query[v]){
			ans_query[q.second] = q.first ^ val[v];
		}
		if(keep)
			T.add(v);
		return;
	}
	for(int u : G[v]){
		if(u != big_child)
			dsu(u, false);
	}
	dsu(big_child, true);
	T.add(v);
	for(int u : G[v]){
		if(u != big_child){
			dfs_add(u);
		}
	}
	for(auto q : query[v]){
		ans_query[q.second] = T.get(q.first, q.second);
	}
	if(!keep)
		T.Clear();
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int Q;
	cin >> Q;
	memset(ans_query, -1, sizeof ans_query);
	int vertex_cnt = 1;
	for(int i = 0; i < Q; i ++){
		string type;
		int x, y;
		cin >> type >> x >> y;
		if(type == "Add"){
			G[--x].push_back(vertex_cnt);
			val[vertex_cnt] = (y ^ val[x]);
			adding_time[vertex_cnt++] = i;
		}
		else{
			query[--y].push_back({val[--x], i});
		}
	}
	dfs_sz(0);
	dsu(0, 0);
	for(int i = 0; i < Q; i ++){
		if(ans_query[i] != -1){
			cout << ans_query[i] << '\n';
		}
	}
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 6 ms 10572 KB Output is correct
3 Correct 6 ms 10572 KB Output is correct
4 Correct 6 ms 10572 KB Output is correct
5 Correct 6 ms 10572 KB Output is correct
6 Correct 6 ms 10572 KB Output is correct
7 Correct 7 ms 10700 KB Output is correct
8 Correct 7 ms 10700 KB Output is correct
9 Correct 6 ms 10572 KB Output is correct
10 Correct 7 ms 10572 KB Output is correct
11 Correct 6 ms 10700 KB Output is correct
12 Correct 6 ms 10700 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 6 ms 10572 KB Output is correct
3 Correct 6 ms 10572 KB Output is correct
4 Correct 6 ms 10572 KB Output is correct
5 Correct 6 ms 10572 KB Output is correct
6 Correct 6 ms 10572 KB Output is correct
7 Correct 7 ms 10700 KB Output is correct
8 Correct 7 ms 10700 KB Output is correct
9 Correct 6 ms 10572 KB Output is correct
10 Correct 7 ms 10572 KB Output is correct
11 Correct 6 ms 10700 KB Output is correct
12 Correct 6 ms 10700 KB Output is correct
13 Correct 8 ms 10828 KB Output is correct
14 Correct 8 ms 11148 KB Output is correct
15 Correct 8 ms 11468 KB Output is correct
16 Correct 9 ms 11724 KB Output is correct
17 Correct 8 ms 11344 KB Output is correct
18 Correct 10 ms 12316 KB Output is correct
19 Correct 11 ms 13340 KB Output is correct
20 Correct 13 ms 14376 KB Output is correct
21 Correct 8 ms 11212 KB Output is correct
22 Correct 9 ms 11752 KB Output is correct
23 Correct 10 ms 12364 KB Output is correct
24 Correct 13 ms 12952 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 38588 KB Output is correct
2 Correct 249 ms 60852 KB Output is correct
3 Correct 276 ms 81576 KB Output is correct
4 Correct 291 ms 102332 KB Output is correct
5 Correct 359 ms 137200 KB Output is correct
6 Correct 584 ms 268724 KB Output is correct
7 Correct 815 ms 395988 KB Output is correct
8 Correct 1054 ms 524288 KB Output is correct
9 Correct 247 ms 69792 KB Output is correct
10 Correct 351 ms 125140 KB Output is correct
11 Correct 404 ms 177720 KB Output is correct
12 Correct 480 ms 229628 KB Output is correct

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 6 ms 10572 KB Output is correct
3 Correct 6 ms 10572 KB Output is correct
4 Correct 6 ms 10572 KB Output is correct
5 Correct 6 ms 10572 KB Output is correct
6 Correct 6 ms 10572 KB Output is correct
7 Correct 7 ms 10700 KB Output is correct
8 Correct 7 ms 10700 KB Output is correct
9 Correct 6 ms 10572 KB Output is correct
10 Correct 7 ms 10572 KB Output is correct
11 Correct 6 ms 10700 KB Output is correct
12 Correct 6 ms 10700 KB Output is correct
13 Correct 8 ms 10828 KB Output is correct
14 Correct 8 ms 11148 KB Output is correct
15 Correct 8 ms 11468 KB Output is correct
16 Correct 9 ms 11724 KB Output is correct
17 Correct 8 ms 11344 KB Output is correct
18 Correct 10 ms 12316 KB Output is correct
19 Correct 11 ms 13340 KB Output is correct
20 Correct 13 ms 14376 KB Output is correct
21 Correct 8 ms 11212 KB Output is correct
22 Correct 9 ms 11752 KB Output is correct
23 Correct 10 ms 12364 KB Output is correct
24 Correct 13 ms 12952 KB Output is correct
25 Correct 207 ms 38588 KB Output is correct
26 Correct 249 ms 60852 KB Output is correct
27 Correct 276 ms 81576 KB Output is correct
28 Correct 291 ms 102332 KB Output is correct
29 Correct 359 ms 137200 KB Output is correct
30 Correct 584 ms 268724 KB Output is correct
31 Correct 815 ms 395988 KB Output is correct
32 Correct 1054 ms 524288 KB Output is correct
33 Correct 247 ms 69792 KB Output is correct
34 Correct 351 ms 125140 KB Output is correct
35 Correct 404 ms 177720 KB Output is correct
36 Correct 480 ms 229628 KB Output is correct
37 Correct 232 ms 39652 KB Output is correct
38 Correct 270 ms 61764 KB Output is correct
39 Correct 305 ms 83060 KB Output is correct
40 Correct 311 ms 102980 KB Output is correct
41 Correct 336 ms 138948 KB Output is correct
42 Correct 590 ms 270568 KB Output is correct
43 Correct 791 ms 387512 KB Output is correct
44 Runtime error 1008 ms 524292 KB Execution killed with signal 9
45 Halted 0 ms 0 KB -