oj.uz

Submission #711540

# Submission time Handle Problem Language Result Execution time Memory
711540 2023-03-17T08:00:58 Z badont Klasika (COCI20_klasika) C++17
33 / 110
 547 ms 214164 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 = 5e5 + 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 32 ms 51200 KB Output is correct
2 Correct 26 ms 51276 KB Output is correct
3 Correct 28 ms 51280 KB Output is correct
4 Correct 26 ms 51412 KB Output is correct
5 Correct 25 ms 51212 KB Output is correct
6 Correct 25 ms 51284 KB Output is correct
7 Correct 25 ms 51284 KB Output is correct
8 Correct 25 ms 51412 KB Output is correct
9 Correct 33 ms 51168 KB Output is correct
10 Correct 29 ms 51304 KB Output is correct
11 Correct 26 ms 51284 KB Output is correct
12 Correct 25 ms 51412 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 51200 KB Output is correct
2 Correct 26 ms 51276 KB Output is correct
3 Correct 28 ms 51280 KB Output is correct
4 Correct 26 ms 51412 KB Output is correct
5 Correct 25 ms 51212 KB Output is correct
6 Correct 25 ms 51284 KB Output is correct
7 Correct 25 ms 51284 KB Output is correct
8 Correct 25 ms 51412 KB Output is correct
9 Correct 33 ms 51168 KB Output is correct
10 Correct 29 ms 51304 KB Output is correct
11 Correct 26 ms 51284 KB Output is correct
12 Correct 25 ms 51412 KB Output is correct
13 Correct 27 ms 51864 KB Output is correct
14 Correct 32 ms 52452 KB Output is correct
15 Correct 32 ms 53112 KB Output is correct
16 Correct 32 ms 53728 KB Output is correct
17 Correct 29 ms 51796 KB Output is correct
18 Correct 39 ms 52460 KB Output is correct
19 Correct 34 ms 53036 KB Output is correct
20 Correct 35 ms 53612 KB Output is correct
21 Correct 33 ms 51752 KB Output is correct
22 Correct 32 ms 52560 KB Output is correct
23 Correct 31 ms 52976 KB Output is correct
24 Correct 32 ms 53564 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 547 ms 214164 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 51200 KB Output is correct
2 Correct 26 ms 51276 KB Output is correct
3 Correct 28 ms 51280 KB Output is correct
4 Correct 26 ms 51412 KB Output is correct
5 Correct 25 ms 51212 KB Output is correct
6 Correct 25 ms 51284 KB Output is correct
7 Correct 25 ms 51284 KB Output is correct
8 Correct 25 ms 51412 KB Output is correct
9 Correct 33 ms 51168 KB Output is correct
10 Correct 29 ms 51304 KB Output is correct
11 Correct 26 ms 51284 KB Output is correct
12 Correct 25 ms 51412 KB Output is correct
13 Correct 27 ms 51864 KB Output is correct
14 Correct 32 ms 52452 KB Output is correct
15 Correct 32 ms 53112 KB Output is correct
16 Correct 32 ms 53728 KB Output is correct
17 Correct 29 ms 51796 KB Output is correct
18 Correct 39 ms 52460 KB Output is correct
19 Correct 34 ms 53036 KB Output is correct
20 Correct 35 ms 53612 KB Output is correct
21 Correct 33 ms 51752 KB Output is correct
22 Correct 32 ms 52560 KB Output is correct
23 Correct 31 ms 52976 KB Output is correct
24 Correct 32 ms 53564 KB Output is correct
25 Runtime error 547 ms 214164 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -