제출 #1326957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326957		goats_9	Klasika (COCI20_klasika)	C++20	110 / 110	1228 ms	312672 KiB

klasika

/* Author: goats_9 */

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Trie {
	enum { D = 30, K = 2 };
	struct Node {
		vector<int> nxt = vector<int> (K, -1);
		int ts = numeric_limits<int>::max();
	};
	vector<Node> tr;
	Trie() : tr(1, Node()) {}
	void add(int x, int t) {
		int cur = 0;
		for (int j = D - 1; j >= 0; j--) {
			int b = x >> j & 1;
			if (tr[cur].nxt[b] == -1) {
				tr[cur].nxt[b] = (int)tr.size();
				tr.push_back(Node());
			}
			cur = tr[cur].nxt[b];
			tr[cur].ts = min(tr[cur].ts, t);
		}
	}
	int query(int x, int t) {
		int cur = 0, ans = x;
		for (int j = D - 1; j >= 0; j--) {
			int b = x >> j & 1;
			b ^= 1;
			if (tr[cur].nxt[b] == -1 || tr[tr[cur].nxt[b]].ts > t) b ^= 1;
			cur = tr[cur].nxt[b];
			ans ^= b << j;
		}
		return ans;
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int q;
	cin >> q;
	vector<int> a(1), t(1);
	vector<pair<int, int>> ans;
	vector<vector<int>> sub(1), g(1);
	vector<vector<pair<int, int>>> qr(1);
	vector<Trie> trie(1);
	for (int i = 0; i < q; i++) {
		string s;
		cin >> s;
		if (s == "Add") {
			int x, y;
			cin >> x >> y;
			--x;
			a.push_back(a[x] ^ y);
			t.push_back(i);
			sub.push_back({});
			g[x].push_back((int)g.size());
			g.push_back({});
			qr.push_back({});
			trie.push_back(Trie());
		} else {
			int x, y;
			cin >> x >> y;
			qr[--y].emplace_back(--x, i);
		}
	}
	auto dfs = [&] (auto&& self, int u) -> void {
		for (auto v : g[u]) self(self, v);
		sort(g[u].rbegin(), g[u].rend(), [&] (int x, int y) { return sub[x].size() < sub[y].size(); });
		if (!g[u].empty()) {
			swap(trie[u], trie[g[u][0]]);
			swap(sub[u], sub[g[u][0]]);
			for (int i = 1; i < (int)g[u].size(); i++) {
				for (auto z : sub[g[u][i]]) trie[u].add(a[z], t[z]);
				sub[u].insert(sub[u].end(), sub[g[u][i]].begin(), sub[g[u][i]].end());
				sub[g[u][i]].clear();
				trie[g[u][i]] = Trie();
			}
		}
		trie[u].add(a[u], t[u]);
		sub[u].push_back(u);
		for (auto [z, i] : qr[u]) ans.emplace_back(i, trie[u].query(a[z], i));
	};
	dfs(dfs, 0);
	sort(ans.begin(), ans.end());
	for (auto [_, z] : ans) cout << z << '\n';
	return 0;
}

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