Submission #482241

#	Time	Username	Problem	Language	Result	Execution time	Memory
482241		danielliu04	Klasika (COCI20_klasika)	C++17	110 / 110	2495 ms	431828 KiB

klasika

// Link: https://judge.yosupo.jp/problem/set_xor_min

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

#define ll long long
#define lc (node<<1)+1
#define rc (node<<1)+2
#define endl '\n'

const int MAX = 2e5+2;
int q;

struct Edge{
	int next, weight;
};

vector<Edge> adj[MAX];

struct Query{
	char type;
	int a, b;
} queries[MAX];


int t = 0;
int enter[MAX];
int out[MAX];
int value[MAX];

void dfs(int node, int curr){
	enter[node] = t++;
	value[node] = curr;
	for(Edge e : adj[node]){
		dfs(e.next, curr ^ e.weight);
	}
	out[node] = t++;
}


struct Vertex{
	Vertex* children[2];
	set<int> entries;
	Vertex(){
		children[0] = nullptr;
		children[1] = nullptr;
	}
};

Vertex* trie;

void insert(Vertex* root, int x, int time){
	Vertex* v = root;
	for(int i = 30; i >= 0; i --){
		bool c = (1 << i) & x;
		if(!v->children[c]) v->children[c] = new Vertex;
		v = v->children[c];
		v->entries.insert(time);
	}
}

int query(Vertex* root, int x, int min_entry, int max_entry){
	Vertex* v = root;
	int ans = 0;
	for(int i = 30; i >= 0; i --){
		bool c = (1 << i) & x;
		c = c^1;
		if(v->children[c]){
			auto a = v->children[c]->entries.lower_bound(min_entry);
			if(a != v->children[c]->entries.end() && *a <= max_entry){
				ans |= (1 << i);
				v = v->children[c];
				continue;
			}
		}

		v = v->children[c^1];
	}
	return ans;
}

int main() {
	
	// cin.tie(0);
	// ios::sync_with_stdio(0);

	cin >> q;

	int counter = 2;
	for(int i = 0; i < q; i ++){
		string s; int a, b;
		cin >> s >> a >> b;
		char type = s[0];
		if(type == 'A'){
			adj[a].push_back({counter ++, b});
		}
		queries[i] = {type, a, b};
	}

	dfs(1, 0);

	// use trie data structure to maintain current values of xor(1, node)
	trie = new Vertex;
	insert(trie, 0, 0);
	counter = 2;
	for(int i = 0; i < q; i ++){
		Query Q = queries[i];
		if(Q.type == 'A'){
			insert(trie, value[counter], enter[counter]);
			counter ++;
		}
		else{
			int ans = query(trie, value[Q.a], enter[Q.b], out[Q.b]);
			cout << ans << endl;
		}
	}

	return 0;
}

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