oj.uz

Submission #711536

# Submission time Handle Problem Language Result Execution time Memory
711536 2023-03-17T07:56:39 Z badont Klasika (COCI20_klasika) C++17
33 / 110
 1747 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 = 3e6 + 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<ll>());
	vector<ll> dp(n);
	vector<ll> 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 138 ms 305592 KB Output is correct
2 Correct 138 ms 305600 KB Output is correct
3 Correct 137 ms 305748 KB Output is correct
4 Correct 134 ms 305736 KB Output is correct
5 Correct 136 ms 305544 KB Output is correct
6 Correct 130 ms 305696 KB Output is correct
7 Correct 137 ms 305704 KB Output is correct
8 Correct 133 ms 305796 KB Output is correct
9 Correct 133 ms 305580 KB Output is correct
10 Correct 133 ms 305712 KB Output is correct
11 Correct 145 ms 305708 KB Output is correct
12 Correct 157 ms 305800 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 305592 KB Output is correct
2 Correct 138 ms 305600 KB Output is correct
3 Correct 137 ms 305748 KB Output is correct
4 Correct 134 ms 305736 KB Output is correct
5 Correct 136 ms 305544 KB Output is correct
6 Correct 130 ms 305696 KB Output is correct
7 Correct 137 ms 305704 KB Output is correct
8 Correct 133 ms 305796 KB Output is correct
9 Correct 133 ms 305580 KB Output is correct
10 Correct 133 ms 305712 KB Output is correct
11 Correct 145 ms 305708 KB Output is correct
12 Correct 157 ms 305800 KB Output is correct
13 Correct 134 ms 306316 KB Output is correct
14 Correct 145 ms 306864 KB Output is correct
15 Correct 141 ms 307568 KB Output is correct
16 Correct 141 ms 308172 KB Output is correct
17 Correct 139 ms 306332 KB Output is correct
18 Correct 156 ms 306796 KB Output is correct
19 Correct 151 ms 307520 KB Output is correct
20 Correct 143 ms 308072 KB Output is correct
21 Correct 148 ms 306208 KB Output is correct
22 Correct 137 ms 306888 KB Output is correct
23 Correct 138 ms 307444 KB Output is correct
24 Correct 148 ms 308064 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 375384 KB Output is correct
2 Correct 1238 ms 438000 KB Output is correct
3 Correct 1747 ms 499676 KB Output is correct
4 Runtime error 1526 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 305592 KB Output is correct
2 Correct 138 ms 305600 KB Output is correct
3 Correct 137 ms 305748 KB Output is correct
4 Correct 134 ms 305736 KB Output is correct
5 Correct 136 ms 305544 KB Output is correct
6 Correct 130 ms 305696 KB Output is correct
7 Correct 137 ms 305704 KB Output is correct
8 Correct 133 ms 305796 KB Output is correct
9 Correct 133 ms 305580 KB Output is correct
10 Correct 133 ms 305712 KB Output is correct
11 Correct 145 ms 305708 KB Output is correct
12 Correct 157 ms 305800 KB Output is correct
13 Correct 134 ms 306316 KB Output is correct
14 Correct 145 ms 306864 KB Output is correct
15 Correct 141 ms 307568 KB Output is correct
16 Correct 141 ms 308172 KB Output is correct
17 Correct 139 ms 306332 KB Output is correct
18 Correct 156 ms 306796 KB Output is correct
19 Correct 151 ms 307520 KB Output is correct
20 Correct 143 ms 308072 KB Output is correct
21 Correct 148 ms 306208 KB Output is correct
22 Correct 137 ms 306888 KB Output is correct
23 Correct 138 ms 307444 KB Output is correct
24 Correct 148 ms 308064 KB Output is correct
25 Correct 767 ms 375384 KB Output is correct
26 Correct 1238 ms 438000 KB Output is correct
27 Correct 1747 ms 499676 KB Output is correct
28 Runtime error 1526 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -