oj.uz

Submission #711537

# Submission time Handle Problem Language Result Execution time Memory
711537 2023-03-17T07:58:28 Z badont Klasika (COCI20_klasika) C++17
33 / 110
 2328 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<ll>());
	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 89 ms 203852 KB Output is correct
2 Correct 90 ms 203916 KB Output is correct
3 Correct 100 ms 203940 KB Output is correct
4 Correct 100 ms 203996 KB Output is correct
5 Correct 94 ms 203780 KB Output is correct
6 Correct 108 ms 203900 KB Output is correct
7 Correct 90 ms 203980 KB Output is correct
8 Correct 95 ms 204068 KB Output is correct
9 Correct 96 ms 203828 KB Output is correct
10 Correct 95 ms 203868 KB Output is correct
11 Correct 110 ms 203956 KB Output is correct
12 Correct 92 ms 204024 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 203852 KB Output is correct
2 Correct 90 ms 203916 KB Output is correct
3 Correct 100 ms 203940 KB Output is correct
4 Correct 100 ms 203996 KB Output is correct
5 Correct 94 ms 203780 KB Output is correct
6 Correct 108 ms 203900 KB Output is correct
7 Correct 90 ms 203980 KB Output is correct
8 Correct 95 ms 204068 KB Output is correct
9 Correct 96 ms 203828 KB Output is correct
10 Correct 95 ms 203868 KB Output is correct
11 Correct 110 ms 203956 KB Output is correct
12 Correct 92 ms 204024 KB Output is correct
13 Correct 99 ms 204540 KB Output is correct
14 Correct 108 ms 205100 KB Output is correct
15 Correct 99 ms 205780 KB Output is correct
16 Correct 99 ms 206484 KB Output is correct
17 Correct 96 ms 204368 KB Output is correct
18 Correct 108 ms 205036 KB Output is correct
19 Correct 101 ms 205592 KB Output is correct
20 Correct 99 ms 206224 KB Output is correct
21 Correct 94 ms 204376 KB Output is correct
22 Correct 108 ms 205008 KB Output is correct
23 Correct 99 ms 205732 KB Output is correct
24 Correct 98 ms 206236 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 724 ms 272404 KB Output is correct
2 Correct 1372 ms 334860 KB Output is correct
3 Correct 1955 ms 396104 KB Output is correct
4 Runtime error 2328 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 89 ms 203852 KB Output is correct
2 Correct 90 ms 203916 KB Output is correct
3 Correct 100 ms 203940 KB Output is correct
4 Correct 100 ms 203996 KB Output is correct
5 Correct 94 ms 203780 KB Output is correct
6 Correct 108 ms 203900 KB Output is correct
7 Correct 90 ms 203980 KB Output is correct
8 Correct 95 ms 204068 KB Output is correct
9 Correct 96 ms 203828 KB Output is correct
10 Correct 95 ms 203868 KB Output is correct
11 Correct 110 ms 203956 KB Output is correct
12 Correct 92 ms 204024 KB Output is correct
13 Correct 99 ms 204540 KB Output is correct
14 Correct 108 ms 205100 KB Output is correct
15 Correct 99 ms 205780 KB Output is correct
16 Correct 99 ms 206484 KB Output is correct
17 Correct 96 ms 204368 KB Output is correct
18 Correct 108 ms 205036 KB Output is correct
19 Correct 101 ms 205592 KB Output is correct
20 Correct 99 ms 206224 KB Output is correct
21 Correct 94 ms 204376 KB Output is correct
22 Correct 108 ms 205008 KB Output is correct
23 Correct 99 ms 205732 KB Output is correct
24 Correct 98 ms 206236 KB Output is correct
25 Correct 724 ms 272404 KB Output is correct
26 Correct 1372 ms 334860 KB Output is correct
27 Correct 1955 ms 396104 KB Output is correct
28 Runtime error 2328 ms 524288 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -