Submission #711544

#	Time	Username	Problem	Language	Result	Execution time	Memory
711544		badont	Klasika (COCI20_klasika)	C++17	33 / 110	2158 ms	524288 KiB

klasika

#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 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44