oj.uz

Submission #711567

# Submission time Handle Problem Language Result Execution time Memory
711567 2023-03-17T08:49:29 Z badont Klasika (COCI20_klasika) C++17
110 / 110
 2357 ms 520892 KB 
#include<bits/stdc++.h>
using namespace std;
 
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
 
#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif
 
using ll = long long;
using ld = long double;
using pii = pair<ll,ll>;
 
#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
 
template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}
 
//var 
ll T;
 struct Node {
	array<set<int>, 2> agg;
	array<Node*, 2> c;

	Node() : agg({set<int>{}, set<int>{}}), c({nullptr, nullptr}) {}
};
void solve() {
	int q; cin >> q;
 
	int n = 1;
	vector<array<int, 3>> queries(q);
	for (auto& [T, x, y] : queries) {
		string s; cin >> s;
		if (s == "Add") T = 0;
		else T = 1;
		cin >> x >> y;
		x--;
		if (T == 0) n++;
		if (T == 1) y--;
	}
 
	int added_in = 1;
	vector e(n, vector<int>());
	vector<int> dp(n);
	vector<int> tin(n), tout(n);
	dp[0] = 0;
	for (const auto& [T, x, y] : queries) {
		if (T == 0) {
			int to = added_in++;
			e[x].pb(to);
			dp[to] = dp[x] ^ y;
		}
	}
 
	int cc = 0;
	auto dfs_euler = [&](auto dfs_euler, int g) -> void {
		tin[g] = cc++;
		for (auto u : e[g]) 
			dfs_euler(dfs_euler, u);
		tout[g] = cc++;
	};
 
	dfs_euler(dfs_euler, 0);
 
	e.clear();
	
 
	Node* root = new Node;
	Node* cur = root;
	for (int i = 29; i >= 0; i--) {
		if (cur->c[0] == nullptr) {
			cur->c[0] = new Node;
		}
		cur->agg[0].insert(0);
		cur = cur->c[0];
	}
 
	int added_recent = 0;
	for (const auto& [T, x, y] : queries) {
		if (T == 0) {
			added_recent++;
			int z = dp[added_recent];
			Node* cur = root;
			int in_set = tin[added_recent];
			for (int i = 29; i >= 0; i--) {
				int b = (z >> i) & 1;
				if (cur->c[b] == nullptr) {
					cur->c[b] = new Node;
				}
				cur->agg[b].insert(in_set);
				cur = cur->c[b];
			}
		} else {
			Node* cur = root;
			int geq = tin[y], les = tout[y];
			int z = dp[x];
			int ans = 0;
			for (int i = 29; i >= 0; i--) {
				int b = (z >> i) & 1;
				int w = b ^ 1;
				auto iter = cur->agg[w].lower_bound(geq);
				if (iter != cur->agg[w].end() and *iter < les) {
					ans ^= (1LL << i);
					cur = cur->c[w];
				} else {
					cur = cur->c[w ^ 1];
				}
			} 
 
			cout << ans << "\n";
		}
	}
}
 
int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);
 
	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();
 
	cout.flush();
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 576 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 2 ms 964 KB Output is correct
5 Correct 1 ms 448 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 1 ms 980 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 576 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 2 ms 964 KB Output is correct
5 Correct 1 ms 448 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 5 ms 2120 KB Output is correct
14 Correct 5 ms 3784 KB Output is correct
15 Correct 6 ms 5332 KB Output is correct
16 Correct 8 ms 6872 KB Output is correct
17 Correct 4 ms 2040 KB Output is correct
18 Correct 5 ms 3668 KB Output is correct
19 Correct 7 ms 5204 KB Output is correct
20 Correct 9 ms 6868 KB Output is correct
21 Correct 4 ms 2004 KB Output is correct
22 Correct 6 ms 3708 KB Output is correct
23 Correct 10 ms 5204 KB Output is correct
24 Correct 11 ms 6696 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 142408 KB Output is correct
2 Correct 1028 ms 271376 KB Output is correct
3 Correct 1443 ms 394144 KB Output is correct
4 Correct 1891 ms 520560 KB Output is correct
5 Correct 653 ms 141332 KB Output is correct
6 Correct 1117 ms 269040 KB Output is correct
7 Correct 1550 ms 390524 KB Output is correct
8 Correct 2357 ms 511476 KB Output is correct
9 Correct 626 ms 140648 KB Output is correct
10 Correct 1073 ms 269532 KB Output is correct
11 Correct 1445 ms 392808 KB Output is correct
12 Correct 1916 ms 512916 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 576 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 2 ms 964 KB Output is correct
5 Correct 1 ms 448 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 5 ms 2120 KB Output is correct
14 Correct 5 ms 3784 KB Output is correct
15 Correct 6 ms 5332 KB Output is correct
16 Correct 8 ms 6872 KB Output is correct
17 Correct 4 ms 2040 KB Output is correct
18 Correct 5 ms 3668 KB Output is correct
19 Correct 7 ms 5204 KB Output is correct
20 Correct 9 ms 6868 KB Output is correct
21 Correct 4 ms 2004 KB Output is correct
22 Correct 6 ms 3708 KB Output is correct
23 Correct 10 ms 5204 KB Output is correct
24 Correct 11 ms 6696 KB Output is correct
25 Correct 609 ms 142408 KB Output is correct
26 Correct 1028 ms 271376 KB Output is correct
27 Correct 1443 ms 394144 KB Output is correct
28 Correct 1891 ms 520560 KB Output is correct
29 Correct 653 ms 141332 KB Output is correct
30 Correct 1117 ms 269040 KB Output is correct
31 Correct 1550 ms 390524 KB Output is correct
32 Correct 2357 ms 511476 KB Output is correct
33 Correct 626 ms 140648 KB Output is correct
34 Correct 1073 ms 269532 KB Output is correct
35 Correct 1445 ms 392808 KB Output is correct
36 Correct 1916 ms 512916 KB Output is correct
37 Correct 992 ms 143052 KB Output is correct
38 Correct 1443 ms 270860 KB Output is correct
39 Correct 1793 ms 396868 KB Output is correct
40 Correct 2024 ms 520892 KB Output is correct
41 Correct 1096 ms 144364 KB Output is correct
42 Correct 1630 ms 271816 KB Output is correct
43 Correct 1885 ms 393740 KB Output is correct
44 Correct 2265 ms 513888 KB Output is correct
45 Correct 1365 ms 143608 KB Output is correct
46 Correct 1838 ms 272440 KB Output is correct
47 Correct 2100 ms 394232 KB Output is correct
48 Correct 2331 ms 516316 KB Output is correct