oj.uz

Submission #711563

# Submission time Handle Problem Language Result Execution time Memory
711563 2023-03-17T08:47:29 Z badont Klasika (COCI20_klasika) C++17
66 / 110
 2289 ms 524288 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() {
	ll q; cin >> q;
 
	ll 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--;
	}
 
	ll 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) {
			ll to = added_in++;
			e[x].pb(to);
			dp[to] = dp[x] ^ y;
		}
	}
 
	ll cc = 0;
	auto dfs_euler = [&](auto dfs_euler, ll 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 = 30; i >= 0; i--) {
		if (cur->c[0] == nullptr) {
			cur->c[0] = new Node;
		}
		cur->agg[0].insert(0);
		cur = cur->c[0];
	}
 
	ll added_recent = 0;
	for (const auto& [T, x, y] : queries) {
		if (T == 0) {
			added_recent++;
			ll z = dp[added_recent];
			Node* cur = root;
			int in_set = tin[added_recent];
			for (int i = 30; 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 = 30; 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 1 ms 576 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 1 ms 444 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 448 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 2 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 1 ms 576 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 1 ms 444 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 448 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 2 ms 980 KB Output is correct
13 Correct 4 ms 2184 KB Output is correct
14 Correct 5 ms 3796 KB Output is correct
15 Correct 7 ms 5376 KB Output is correct
16 Correct 8 ms 6868 KB Output is correct
17 Correct 5 ms 2004 KB Output is correct
18 Correct 7 ms 3668 KB Output is correct
19 Correct 7 ms 5344 KB Output is correct
20 Correct 12 ms 6740 KB Output is correct
21 Correct 5 ms 2004 KB Output is correct
22 Correct 5 ms 3704 KB Output is correct
23 Correct 6 ms 5324 KB Output is correct
24 Correct 8 ms 6868 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 145060 KB Output is correct
2 Correct 1165 ms 275864 KB Output is correct
3 Correct 1562 ms 400224 KB Output is correct
4 Correct 2133 ms 524288 KB Output is correct
5 Correct 698 ms 145804 KB Output is correct
6 Correct 1116 ms 275668 KB Output is correct
7 Correct 1627 ms 399292 KB Output is correct
8 Correct 2170 ms 522472 KB Output is correct
9 Correct 682 ms 145008 KB Output is correct
10 Correct 1141 ms 276396 KB Output is correct
11 Correct 1469 ms 401596 KB Output is correct
12 Correct 2015 ms 523988 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 576 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 1 ms 444 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 448 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 2 ms 980 KB Output is correct
13 Correct 4 ms 2184 KB Output is correct
14 Correct 5 ms 3796 KB Output is correct
15 Correct 7 ms 5376 KB Output is correct
16 Correct 8 ms 6868 KB Output is correct
17 Correct 5 ms 2004 KB Output is correct
18 Correct 7 ms 3668 KB Output is correct
19 Correct 7 ms 5344 KB Output is correct
20 Correct 12 ms 6740 KB Output is correct
21 Correct 5 ms 2004 KB Output is correct
22 Correct 5 ms 3704 KB Output is correct
23 Correct 6 ms 5324 KB Output is correct
24 Correct 8 ms 6868 KB Output is correct
25 Correct 651 ms 145060 KB Output is correct
26 Correct 1165 ms 275864 KB Output is correct
27 Correct 1562 ms 400224 KB Output is correct
28 Correct 2133 ms 524288 KB Output is correct
29 Correct 698 ms 145804 KB Output is correct
30 Correct 1116 ms 275668 KB Output is correct
31 Correct 1627 ms 399292 KB Output is correct
32 Correct 2170 ms 522472 KB Output is correct
33 Correct 682 ms 145008 KB Output is correct
34 Correct 1141 ms 276396 KB Output is correct
35 Correct 1469 ms 401596 KB Output is correct
36 Correct 2015 ms 523988 KB Output is correct
37 Correct 1070 ms 148240 KB Output is correct
38 Correct 1635 ms 278036 KB Output is correct
39 Correct 2156 ms 406132 KB Output is correct
40 Runtime error 2289 ms 524288 KB Execution killed with signal 9
41 Halted 0 ms 0 KB -