제출 #1176615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1176615		euthymia2606	Klasika (COCI20_klasika)	C++17	110 / 110	1600 ms	471664 KiB

klasika

#include <bits/stdc++.h> 

using namespace std;  

typedef long long ll;  
typedef pair<int, int> ii;  

const int INF = 1e9;  
const ll LINF = 1e18;  

const int N = 2e5 + 5; 
const int Q = 2e5 + 5; 

struct Query {
	int type, u, v; 
}; 

int n, q;  
vector<int> adj[N]; 
vector<Query> queries;  

int dist[N]; 
int tin[N], tout[N], timer;  

void dfs(int u, int p) {
	tin[u] = ++timer;  
	for (int v : adj[u]) {
		if (v == p) continue;  
		dfs(v, u); 
	}
	tout[u] = timer; 
}

struct Trie {
	struct Node {
		int nxt[2];  
		set<int> s;  

		Node() {
			memset(nxt, 0, sizeof nxt); 
		}
	};

	vector<Node> t;  

	Trie() {
		t = vector<Node>(1); 
	}

	void add(int x) {
		int v = 0;  
		for (int i = 30; i >= 0; i--) {
			int c = (dist[x] >> i) & 1; 
			if (t[v].nxt[c] == 0) {
				t[v].nxt[c] = t.size(); 
				t.push_back(Node()); 
			}
			v = t[v].nxt[c];
			t[v].s.insert(tin[x]);  
		}
	}

	int getMaxXor(int x, int y) {
		int v = 0;  
		int ans = 0;  
		for (int i = 30; i >= 0; i--) {
			int c = (dist[x] >> i) & 1; 
			int nxt_v0 = t[v].nxt[c], nxt_v1 = t[v].nxt[c ^ 1];  
			auto it = t[nxt_v1].s.lower_bound(tin[y]); 
			if (it != t[nxt_v1].s.end() && (*it) <= tout[y]) {
				ans |= (1 << i);  
				v = nxt_v1; 
			}
			else {
				v = nxt_v0; 
			}
		}
		return ans; 
	}
}; 

int main() {
	ios::sync_with_stdio(false); 
	cin.tie(nullptr); 	
	cin >> q; 

	n = 1;
	dist[1] = 0;    
	for (int i = 0; i < q; i++) {
		string type; cin >> type; 
		if (type == "Add") {
			int p, val; 
			cin >> p >> val;  
			int u = ++n;   
			adj[p].push_back(u);  
			adj[u].push_back(p); 
			dist[u] = dist[p] ^ val;
			queries.push_back({1, u});  
		}
		else {
			int u, v; 
			cin >> u >> v;  
			queries.push_back({2, u, v}); 
		}
	}

	timer = 0;  
	dfs(1, -1);

	Trie trie;  
	trie.add(1);
	for (int i = 0; i < q; i++) {
		int type = queries[i].type; 
		int u = queries[i].u;  
		if (type == 1) {
			trie.add(u); 
		}
		else {
			int v = queries[i].v;  
			int ans = trie.getMaxXor(u, v); 
			cout << ans << '\n'; 
		}
	}
}

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