oj.uz

Submission #531447

# Submission time Handle Problem Language Result Execution time Memory
531447 2022-02-28T17:29:53 Z fcw Klasika (COCI20_klasika) C++17
110 / 110
 3274 ms 478452 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
	return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;

const int K = 31;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int q;
	cin>>q;
	vector<array<int, 3>>qr(q);
	vector<vector<int>>g(1);
	int n = 1;
	for(int i=0;i<q;i++){
		string a;
		int x, y;
		cin>>a>>x>>y;
		int t = (a == "Add") ? 0 : 1;
		if(!t) x--;
		else x--, y--;
		if(!t){
			g[x].push_back(n++);
			g.push_back({});
		}
		qr[i] = {t, x, y};
	}
	vector<int>tin(n), tout(n);
	int timer = 0;
	auto dfs = [&](auto& self, int u) -> void{
		tin[u] = ++timer;
		for(int v : g[u]){
			self(self, v);
		}
		tout[u] = timer;
	};
	dfs(dfs, 0);
	vector<int>path(n);
	vector<array<int, 2>>trie(1, {-1, -1});
	vector<set<int>>s(1);
	auto add = [&](int u, int t) ->void{
		int cur = 0;
		for(int a=K;a>=0;a--){
			int b = u>>a&1;
			if(trie[cur][b] == -1){
				trie[cur][b] = (int)trie.size();
				trie.push_back({-1, -1});
				s.push_back({});
			}
			cur = trie[cur][b];
			s[cur].insert(t);
		}
	};
	add(0, tin[0]);
	int id = 1;
	for(auto [t, x, y] : qr){
		if(t == 0){
			path[id] = path[x] ^ y;
			add(path[id], tin[id]);
			id++;
		}
		else{
			int w = path[x];
			int cur = 0, mask = 0;
			for(int a=K;a>=0;a--){
				int b = w>>a&1;
				if(trie[cur][!b] == -1){
					cur = trie[cur][b];
				}
				else{
					int nxt = trie[cur][!b];
					auto it = s[nxt].lower_bound(tin[y]);
					if(it == s[nxt].end() || (*it) > tout[y]){
						cur = trie[cur][b];
					}
					else{
						mask |= (1<<a);
						cur = trie[cur][!b];
					}
				}
			}
			cout<<mask<<"\n";
		}
	}

	return 0;
}
/*
[  ]Leu o problema certo???
[  ]Ver se precisa de long long
[  ]Viu o limite dos fors (é n? é m?)
[  ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[  ]Testar sample
[  ]Testar casos de  borda
[  ]1LL no 1LL << i
[  ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 720 KB Output is correct
8 Correct 1 ms 720 KB Output is correct
9 Correct 1 ms 440 KB Output is correct
10 Correct 1 ms 696 KB Output is correct
11 Correct 1 ms 720 KB Output is correct
12 Correct 1 ms 720 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 720 KB Output is correct
8 Correct 1 ms 720 KB Output is correct
9 Correct 1 ms 440 KB Output is correct
10 Correct 1 ms 696 KB Output is correct
11 Correct 1 ms 720 KB Output is correct
12 Correct 1 ms 720 KB Output is correct
13 Correct 4 ms 1860 KB Output is correct
14 Correct 5 ms 3336 KB Output is correct
15 Correct 7 ms 3716 KB Output is correct
16 Correct 9 ms 6532 KB Output is correct
17 Correct 4 ms 1804 KB Output is correct
18 Correct 6 ms 3336 KB Output is correct
19 Correct 11 ms 3588 KB Output is correct
20 Correct 9 ms 4604 KB Output is correct
21 Correct 4 ms 1788 KB Output is correct
22 Correct 6 ms 3336 KB Output is correct
23 Correct 7 ms 3604 KB Output is correct
24 Correct 8 ms 4612 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 117020 KB Output is correct
2 Correct 1321 ms 234520 KB Output is correct
3 Correct 2025 ms 291104 KB Output is correct
4 Correct 2633 ms 478452 KB Output is correct
5 Correct 844 ms 115408 KB Output is correct
6 Correct 1568 ms 230932 KB Output is correct
7 Correct 2413 ms 286648 KB Output is correct
8 Correct 3248 ms 471256 KB Output is correct
9 Correct 858 ms 115736 KB Output is correct
10 Correct 1517 ms 231592 KB Output is correct
11 Correct 2025 ms 288880 KB Output is correct
12 Correct 2908 ms 472828 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 464 KB Output is correct
7 Correct 1 ms 720 KB Output is correct
8 Correct 1 ms 720 KB Output is correct
9 Correct 1 ms 440 KB Output is correct
10 Correct 1 ms 696 KB Output is correct
11 Correct 1 ms 720 KB Output is correct
12 Correct 1 ms 720 KB Output is correct
13 Correct 4 ms 1860 KB Output is correct
14 Correct 5 ms 3336 KB Output is correct
15 Correct 7 ms 3716 KB Output is correct
16 Correct 9 ms 6532 KB Output is correct
17 Correct 4 ms 1804 KB Output is correct
18 Correct 6 ms 3336 KB Output is correct
19 Correct 11 ms 3588 KB Output is correct
20 Correct 9 ms 4604 KB Output is correct
21 Correct 4 ms 1788 KB Output is correct
22 Correct 6 ms 3336 KB Output is correct
23 Correct 7 ms 3604 KB Output is correct
24 Correct 8 ms 4612 KB Output is correct
25 Correct 704 ms 117020 KB Output is correct
26 Correct 1321 ms 234520 KB Output is correct
27 Correct 2025 ms 291104 KB Output is correct
28 Correct 2633 ms 478452 KB Output is correct
29 Correct 844 ms 115408 KB Output is correct
30 Correct 1568 ms 230932 KB Output is correct
31 Correct 2413 ms 286648 KB Output is correct
32 Correct 3248 ms 471256 KB Output is correct
33 Correct 858 ms 115736 KB Output is correct
34 Correct 1517 ms 231592 KB Output is correct
35 Correct 2025 ms 288880 KB Output is correct
36 Correct 2908 ms 472828 KB Output is correct
37 Correct 1150 ms 117652 KB Output is correct
38 Correct 1776 ms 234852 KB Output is correct
39 Correct 2253 ms 293648 KB Output is correct
40 Correct 2805 ms 478436 KB Output is correct
41 Correct 1358 ms 115680 KB Output is correct
42 Correct 2139 ms 231276 KB Output is correct
43 Correct 2678 ms 286824 KB Output is correct
44 Correct 3274 ms 471692 KB Output is correct
45 Correct 1375 ms 116312 KB Output is correct
46 Correct 2109 ms 231944 KB Output is correct
47 Correct 2760 ms 287660 KB Output is correct
48 Correct 3049 ms 473024 KB Output is correct