Submission #711563

#	Time	Username	Problem	Language	Result	Execution time	Memory
711563		badont	Klasika (COCI20_klasika)	C++17	66 / 110	2289 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 << "]";
}
 
//var 
ll T;
 struct Node {
	array<set<int>, 2> agg;
	array<Node*, 2> c;

	Node() : agg({set<int>{}, set<int>{}}), c({nullptr, nullptr}) {}
};
void solve() {
	ll q; cin >> q;
 
	ll n = 1;
	vector<array<int, 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);
 
	e.clear();
	
 
	Node* root = new Node;
	Node* cur = root;
	for (int i = 30; i >= 0; i--) {
		if (cur->c[0] == nullptr) {
			cur->c[0] = new Node;
		}
		cur->agg[0].insert(0);
		cur = cur->c[0];
	}
 
	ll added_recent = 0;
	for (const auto& [T, x, y] : queries) {
		if (T == 0) {
			added_recent++;
			ll z = dp[added_recent];
			Node* cur = root;
			int in_set = tin[added_recent];
			for (int i = 30; i >= 0; i--) {
				int b = (z >> i) & 1;
				if (cur->c[b] == nullptr) {
					cur->c[b] = new Node;
				}
				cur->agg[b].insert(in_set);
				cur = cur->c[b];
			}
		} else {
			Node* cur = root;
			int geq = tin[y], les = tout[y];
			int z = dp[x];
			int ans = 0;
			for (int i = 30; i >= 0; i--) {
				int b = (z >> i) & 1;
				int w = b ^ 1;
				auto iter = cur->agg[w].lower_bound(geq);
				if (iter != cur->agg[w].end() and *iter < les) {
					ans ^= (1LL << i);
					cur = cur->c[w];
				} else {
					cur = 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: 33 / 33
• Subtask 4: 0 / 44