Submission #1319265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319265		sonarcht	Klasika (COCI20_klasika)	C++20	33 / 110	720 ms	589824 KiB

klasika

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(v) begin(v), end(v)
#define pll pair<ll, ll>
#define fi first
#define se second
#define vll vector<ll>
#define mll map<ll, ll>
//mt19937_64 rng(chrono::high_resolution_clock().now().ti_since_epoch().count());
const ll N = 2e5 + 6, inf = 1e18 + 7, mod = 1e9 + 7;
ll n, m, k, q, ans[N], a[N], pf[N], ti[N];
vector<pll> qry[N];

struct Trie {
	struct Node {
		Node* child[2];
		ll ti;
		Node() {
			child[0] = child[1] = nullptr;
			ti = inf;
		}
	};
	Node* root;
	Trie() {
		root = new Node();
	}
	vector<pll> v;
	void insert(ll x, ll t) {
		v.pb({x, t});
		Node* node = root;
		for (int j = 30; j >= 0; --j) {
			ll b = x >> j & 1;
			if (!node->child[b]) node->child[b] = new Node();
			node = node->child[b];
			node->ti = min(node->ti, t);
		}
	}
	ll search(ll x, ll t) {
		Node* node = root;
		ll ans = 0;
		for (int j = 30; j >= 0; --j) {
			ll b = x >> j & 1;
			if (node->child[!b] && node->child[!b]->ti <= t) {
				ans |= (1 << j);
				node = node->child[!b];
			} else node = node->child[b];
		}
		return ans;
	}
	friend void swap(Trie &a, Trie &b) {
		using std::swap;
		swap(a.root, b.root);
		swap(a.v, b.v);
	}
} tr[N];

vll adj[N];
void dfs(ll p, ll u) {
	for (ll v : adj[u]) {
		if (v == p) continue;
		dfs(u, v);
		if (tr[u].v.size() < tr[v].v.size()) swap(tr[u], tr[v]);
		for (auto i : tr[v].v) tr[u].insert(i.fi, i.se);
	}
	tr[u].insert(pf[u], ti[u]);
	for (auto [x, i] : qry[u]) {
		ans[i] = tr[u].search(pf[x], i);
	}
}

void solve() {
	cin >> q;
	n = 1;
	for (int i = 1; i <= q; ++i) {
		string tp;
		ll x, y;
		cin >> tp >> x >> y;
		if (tp == "Add") {
			adj[x].pb(++n);
			adj[n].pb(x);
			ti[n] = i;
			pf[n] = pf[x] ^ y;
		} else {
			qry[y].pb({x, i});
		}
	}
	fill(ans, ans+N, inf);
	dfs(-1, 1);
	for (int i = 1; i <= q; ++i) {
		if (ans[i] != inf) cout << ans[i] << endl;
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	if (fopen(".INP", "r")) {
		freopen(".INP", "r", stdin);
		freopen(".OUT", "w", stdout);
	}
	ll tc = 1;
//	cin >> tc;
	while (tc--) {
		solve();
	}
	return 0;
}

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:104:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |                 freopen(".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
klasika.cpp:105:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |                 freopen(".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44