oj.uz

Submission #642193

# Submission time Handle Problem Language Result Execution time Memory
642193 2022-09-18T18:52:44 Z thiago_bastos Klasika (COCI20_klasika) C++17
110 / 110
 2615 ms 475368 KB 
#include "bits/stdc++.h"

using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;

const int N = 2e5 + 100;

vector<ii> adj[N];
int in[N], out[N], z[N], tms;

void dfs(int u) {
	in[u] = tms++;
	for(auto [v, w] : adj[u]) {
		z[v] = z[u] ^ w;
		dfs(v);
	}
	out[u] = tms - 1;
}

struct Node {
	int next[2];
	set<int> s;
	Node() {
		next[0] = next[1] = -1;
	}
};

vector<Node> t(1);

void push(int u) {
	int i = 0;
	for(int j = 29; j >= 0; --j) {
		int c = (z[u] >> j) & 1;
		if(t[i].next[c] < 0) {
			t[i].next[c] = t.size();
			t.emplace_back();
		}
		t[i].s.insert(in[u]);
		i = t[i].next[c];
	}
	t[i].s.insert(in[u]);
}

bool has_child_in(int u, int k) {
	if(k < 0) return false;
	auto& s = t[k].s;
	auto it = s.lower_bound(in[u]);
	return it != s.end() && *it <= out[u]; 
}

void solve() {
	int n = 1, q;

	cin >> q;

	vector<tuple<int, int, int>> query(q);

	for(int i = 0; i < q; ++i) {
		string type;
		int a, b;
		cin >> type >> a >> b;
		query[i] = {type == "Query", a, b};
		if(type == "Add") {
			++n;
			adj[a].emplace_back(n, b); 
		}
	}

	dfs(1);

	push(1);

	n = 1;

	for(auto [type, a, b] : query) {
		if(type == 0) {
			++n;
			push(n);
		} else {
			int ans = 0;
			for(int i = 0, j = 29; j >= 0; --j) {
				int c = (z[a] >> j) & 1;
				if(has_child_in(b, t[i].next[c ^ 1])) {
					ans ^= 1 << j;
					i = t[i].next[c ^ 1];
				} else
					i = t[i].next[c];
			}
			cout << ans << '\n';
		}
	}
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5156 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 3 ms 5460 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5408 KB Output is correct
8 Correct 3 ms 5408 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 3 ms 5332 KB Output is correct
11 Correct 3 ms 5460 KB Output is correct
12 Correct 3 ms 5412 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5156 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 3 ms 5460 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5408 KB Output is correct
8 Correct 3 ms 5408 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 3 ms 5332 KB Output is correct
11 Correct 3 ms 5460 KB Output is correct
12 Correct 3 ms 5412 KB Output is correct
13 Correct 5 ms 6512 KB Output is correct
14 Correct 7 ms 7980 KB Output is correct
15 Correct 8 ms 8324 KB Output is correct
16 Correct 11 ms 11176 KB Output is correct
17 Correct 6 ms 6472 KB Output is correct
18 Correct 8 ms 7944 KB Output is correct
19 Correct 8 ms 8200 KB Output is correct
20 Correct 10 ms 9256 KB Output is correct
21 Correct 8 ms 6512 KB Output is correct
22 Correct 7 ms 7980 KB Output is correct
23 Correct 9 ms 8232 KB Output is correct
24 Correct 10 ms 9256 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 120064 KB Output is correct
2 Correct 1127 ms 235440 KB Output is correct
3 Correct 1583 ms 289728 KB Output is correct
4 Correct 2195 ms 475300 KB Output is correct
5 Correct 708 ms 117556 KB Output is correct
6 Correct 1238 ms 230784 KB Output is correct
7 Correct 1719 ms 283420 KB Output is correct
8 Correct 2333 ms 465628 KB Output is correct
9 Correct 643 ms 118084 KB Output is correct
10 Correct 1126 ms 231492 KB Output is correct
11 Correct 1603 ms 285600 KB Output is correct
12 Correct 2129 ms 467268 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5156 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 3 ms 5460 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5408 KB Output is correct
8 Correct 3 ms 5408 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 3 ms 5332 KB Output is correct
11 Correct 3 ms 5460 KB Output is correct
12 Correct 3 ms 5412 KB Output is correct
13 Correct 5 ms 6512 KB Output is correct
14 Correct 7 ms 7980 KB Output is correct
15 Correct 8 ms 8324 KB Output is correct
16 Correct 11 ms 11176 KB Output is correct
17 Correct 6 ms 6472 KB Output is correct
18 Correct 8 ms 7944 KB Output is correct
19 Correct 8 ms 8200 KB Output is correct
20 Correct 10 ms 9256 KB Output is correct
21 Correct 8 ms 6512 KB Output is correct
22 Correct 7 ms 7980 KB Output is correct
23 Correct 9 ms 8232 KB Output is correct
24 Correct 10 ms 9256 KB Output is correct
25 Correct 610 ms 120064 KB Output is correct
26 Correct 1127 ms 235440 KB Output is correct
27 Correct 1583 ms 289728 KB Output is correct
28 Correct 2195 ms 475300 KB Output is correct
29 Correct 708 ms 117556 KB Output is correct
30 Correct 1238 ms 230784 KB Output is correct
31 Correct 1719 ms 283420 KB Output is correct
32 Correct 2333 ms 465628 KB Output is correct
33 Correct 643 ms 118084 KB Output is correct
34 Correct 1126 ms 231492 KB Output is correct
35 Correct 1603 ms 285600 KB Output is correct
36 Correct 2129 ms 467268 KB Output is correct
37 Correct 1062 ms 120576 KB Output is correct
38 Correct 1599 ms 235948 KB Output is correct
39 Correct 2021 ms 291944 KB Output is correct
40 Correct 2305 ms 475368 KB Output is correct
41 Correct 1220 ms 118024 KB Output is correct
42 Correct 1707 ms 231020 KB Output is correct
43 Correct 2120 ms 283352 KB Output is correct
44 Correct 2615 ms 465932 KB Output is correct
45 Correct 1228 ms 118476 KB Output is correct
46 Correct 1819 ms 231964 KB Output is correct
47 Correct 2158 ms 284372 KB Output is correct
48 Correct 2464 ms 467516 KB Output is correct