oj.uz

Submission #711544

# Submission time Handle Problem Language Result Execution time Memory
711544 2023-03-17T08:07:43 Z badont Klasika (COCI20_klasika) C++17
33 / 110
 2158 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 << "]";
}

struct Node {
	array<set<int>, 2> agg;
	array<int, 2> c;

	Node() : agg({set<int>{}, set<int>{}}), c({-1, -1}) {}
};

static constexpr int LIM = 2e6 + 6;
Node a[LIM];

//var 
ll T;

void solve() {
	ll q; cin >> q;

	ll n = 1;
	vector<array<ll, 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);

	

	int root = 0;
	int cur = root;
	int nxt = 1;
	for (int i = 30; i >= 0; i--) {
		if (a[cur].c[0] == -1) {
			a[cur].c[0] = nxt++;
		}
		a[cur].agg[0].insert(0);
		cur = a[cur].c[0];
	}

	ll added_recent = 0;
	for (const auto& [T, x, y] : queries) {
		if (T == 0) {
			added_recent++;
			ll z = dp[added_recent];
			int cur = root;
			int in_set = tin[added_recent];
			for (int i = 30; i >= 0; i--) {
				int b = (z >> i) & 1;
				if (a[cur].c[b] == -1) {
					a[cur].c[b] = nxt++;
				}
				a[cur].agg[b].insert(in_set);
				cur = a[cur].c[b];
			}
		} else {
			int cur = root;
			ll geq = tin[y], les = tout[y];
			ll z = dp[x];
			ll ans = 0;
			for (int i = 30; i >= 0; i--) {
				int b = (z >> i) & 1;
				int w = b ^ 1;
				auto iter = a[cur].agg[w].lower_bound(geq);
				if (iter != a[cur].agg[w].end() and *iter < les) {
					ans ^= (1LL << i);
					cur = a[cur].c[w];
				} else {
					cur = a[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 102 ms 203860 KB Output is correct
2 Correct 100 ms 203948 KB Output is correct
3 Correct 95 ms 203896 KB Output is correct
4 Correct 94 ms 204048 KB Output is correct
5 Correct 101 ms 203816 KB Output is correct
6 Correct 100 ms 203932 KB Output is correct
7 Correct 96 ms 203956 KB Output is correct
8 Correct 101 ms 204004 KB Output is correct
9 Correct 97 ms 203852 KB Output is correct
10 Correct 104 ms 203920 KB Output is correct
11 Correct 104 ms 203928 KB Output is correct
12 Correct 107 ms 204000 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 203860 KB Output is correct
2 Correct 100 ms 203948 KB Output is correct
3 Correct 95 ms 203896 KB Output is correct
4 Correct 94 ms 204048 KB Output is correct
5 Correct 101 ms 203816 KB Output is correct
6 Correct 100 ms 203932 KB Output is correct
7 Correct 96 ms 203956 KB Output is correct
8 Correct 101 ms 204004 KB Output is correct
9 Correct 97 ms 203852 KB Output is correct
10 Correct 104 ms 203920 KB Output is correct
11 Correct 104 ms 203928 KB Output is correct
12 Correct 107 ms 204000 KB Output is correct
13 Correct 96 ms 204516 KB Output is correct
14 Correct 97 ms 205092 KB Output is correct
15 Correct 98 ms 205784 KB Output is correct
16 Correct 100 ms 206292 KB Output is correct
17 Correct 101 ms 204412 KB Output is correct
18 Correct 99 ms 204988 KB Output is correct
19 Correct 95 ms 205716 KB Output is correct
20 Correct 108 ms 206220 KB Output is correct
21 Correct 92 ms 204436 KB Output is correct
22 Correct 94 ms 205028 KB Output is correct
23 Correct 96 ms 205628 KB Output is correct
24 Correct 107 ms 206288 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 780 ms 272480 KB Output is correct
2 Correct 1278 ms 334908 KB Output is correct
3 Correct 1753 ms 396032 KB Output is correct
4 Runtime error 2158 ms 524288 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 203860 KB Output is correct
2 Correct 100 ms 203948 KB Output is correct
3 Correct 95 ms 203896 KB Output is correct
4 Correct 94 ms 204048 KB Output is correct
5 Correct 101 ms 203816 KB Output is correct
6 Correct 100 ms 203932 KB Output is correct
7 Correct 96 ms 203956 KB Output is correct
8 Correct 101 ms 204004 KB Output is correct
9 Correct 97 ms 203852 KB Output is correct
10 Correct 104 ms 203920 KB Output is correct
11 Correct 104 ms 203928 KB Output is correct
12 Correct 107 ms 204000 KB Output is correct
13 Correct 96 ms 204516 KB Output is correct
14 Correct 97 ms 205092 KB Output is correct
15 Correct 98 ms 205784 KB Output is correct
16 Correct 100 ms 206292 KB Output is correct
17 Correct 101 ms 204412 KB Output is correct
18 Correct 99 ms 204988 KB Output is correct
19 Correct 95 ms 205716 KB Output is correct
20 Correct 108 ms 206220 KB Output is correct
21 Correct 92 ms 204436 KB Output is correct
22 Correct 94 ms 205028 KB Output is correct
23 Correct 96 ms 205628 KB Output is correct
24 Correct 107 ms 206288 KB Output is correct
25 Correct 780 ms 272480 KB Output is correct
26 Correct 1278 ms 334908 KB Output is correct
27 Correct 1753 ms 396032 KB Output is correct
28 Runtime error 2158 ms 524288 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -