oj.uz

Submission #711542

# Submission time Handle Problem Language Result Execution time Memory
711542 2023-03-17T08:01:34 Z badont Klasika (COCI20_klasika) C++17
33 / 110
 962 ms 430208 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 = 1e6 + 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 48 ms 102076 KB Output is correct
2 Correct 57 ms 102068 KB Output is correct
3 Correct 47 ms 102144 KB Output is correct
4 Correct 52 ms 102260 KB Output is correct
5 Correct 47 ms 102092 KB Output is correct
6 Correct 46 ms 102092 KB Output is correct
7 Correct 48 ms 102220 KB Output is correct
8 Correct 47 ms 102256 KB Output is correct
9 Correct 50 ms 102044 KB Output is correct
10 Correct 47 ms 102224 KB Output is correct
11 Correct 48 ms 102224 KB Output is correct
12 Correct 47 ms 102204 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 102076 KB Output is correct
2 Correct 57 ms 102068 KB Output is correct
3 Correct 47 ms 102144 KB Output is correct
4 Correct 52 ms 102260 KB Output is correct
5 Correct 47 ms 102092 KB Output is correct
6 Correct 46 ms 102092 KB Output is correct
7 Correct 48 ms 102220 KB Output is correct
8 Correct 47 ms 102256 KB Output is correct
9 Correct 50 ms 102044 KB Output is correct
10 Correct 47 ms 102224 KB Output is correct
11 Correct 48 ms 102224 KB Output is correct
12 Correct 47 ms 102204 KB Output is correct
13 Correct 57 ms 102732 KB Output is correct
14 Correct 53 ms 103372 KB Output is correct
15 Correct 50 ms 103928 KB Output is correct
16 Correct 51 ms 104516 KB Output is correct
17 Correct 50 ms 102604 KB Output is correct
18 Correct 49 ms 103332 KB Output is correct
19 Correct 51 ms 103916 KB Output is correct
20 Correct 52 ms 104452 KB Output is correct
21 Correct 52 ms 102812 KB Output is correct
22 Correct 53 ms 103236 KB Output is correct
23 Correct 51 ms 103860 KB Output is correct
24 Correct 54 ms 104524 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 170796 KB Output is correct
2 Runtime error 962 ms 430208 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 102076 KB Output is correct
2 Correct 57 ms 102068 KB Output is correct
3 Correct 47 ms 102144 KB Output is correct
4 Correct 52 ms 102260 KB Output is correct
5 Correct 47 ms 102092 KB Output is correct
6 Correct 46 ms 102092 KB Output is correct
7 Correct 48 ms 102220 KB Output is correct
8 Correct 47 ms 102256 KB Output is correct
9 Correct 50 ms 102044 KB Output is correct
10 Correct 47 ms 102224 KB Output is correct
11 Correct 48 ms 102224 KB Output is correct
12 Correct 47 ms 102204 KB Output is correct
13 Correct 57 ms 102732 KB Output is correct
14 Correct 53 ms 103372 KB Output is correct
15 Correct 50 ms 103928 KB Output is correct
16 Correct 51 ms 104516 KB Output is correct
17 Correct 50 ms 102604 KB Output is correct
18 Correct 49 ms 103332 KB Output is correct
19 Correct 51 ms 103916 KB Output is correct
20 Correct 52 ms 104452 KB Output is correct
21 Correct 52 ms 102812 KB Output is correct
22 Correct 53 ms 103236 KB Output is correct
23 Correct 51 ms 103860 KB Output is correct
24 Correct 54 ms 104524 KB Output is correct
25 Correct 654 ms 170796 KB Output is correct
26 Runtime error 962 ms 430208 KB Execution killed with signal 11
27 Halted 0 ms 0 KB -