Submission #197995

#	Time	Username	Problem	Language	Result	Execution time	Memory
197995		ami	Klasika (COCI20_klasika)	C++17	110 / 110	1419 ms	209800 KiB

klasika

#include <bits/stdc++.h>
#define sz(c)       int(c.size())
#define rep(i,a,b)  for (int i=a; i<(b); ++i)
#define per(i,a,b)  for (int i=(b)-1; i>=(a); --i)
#define fore(c,...) for (auto __VA_ARGS__:(c))
using namespace std;
typedef long long ll;
int const inf=(int)1e9;

template<class T> bool umin(T &x,T y) { if (x<y) return 0; x=y; return 1; }
template<class T> bool umax(T &x,T y) { if (x>y) return 0; x=y; return 1; }

struct trie_node {
	int next[2];
	int mint[2];
	trie_node() {
		memset(next,~0,sizeof(next));
		mint[0]=mint[1]=inf;
	}
};

struct trie {
	static constexpr int bitlen=30;

	vector<trie_node> t;
	trie():t(1) {}

	void new_node(int v,int bit) {
		t[v].next[bit]=sz(t);
		t.emplace_back();
	}

	void add(int x,int time) {
		int v=0;
		per(i,0,bitlen+1) {
			int bit=x>>i&1;
			if (t[v].next[bit]==-1) new_node(v,bit);
			umin(t[v].mint[bit],time);
			v=t[v].next[bit];
		}
	}

	int getmax(int x,int time) {
		int v=0,res=0;
		per(i,0,bitlen+1) {
			int bit=x>>i&1;
			if (t[v].next[!bit]!=-1 && t[v].mint[!bit]<time) {
				res^=1<<i;
				bit=!bit;
			}
			if (t[v].next[bit]==-1 || t[v].mint[bit]>time) return 0;
			v=t[v].next[bit];
		}
		return res;
	}

	void merge(trie &other) {
		if (sz(t)<sz(other.t)) t.swap(other.t);
		function<void(int,int,int,int)> dfs=[&](int v,int o,int i,int x) {
			rep(bit,0,2) if (other.t[o].next[bit]!=-1) {
				if (t[v].next[bit]==-1) new_node(v,bit);
				umin(t[v].mint[bit],other.t[o].mint[bit]);
				dfs(t[v].next[bit], other.t[o].next[bit], i-1, x|(bit<<i));
			}
		};
		dfs(0,0,bitlen,0);
		vector<trie_node>().swap(other.t);
	}
};

struct node {
	int xum;
	vector<int> adj;
	vector<pair<int,int>> que;
	trie tri;

	node(int x=0,int t=0):xum(x) {
		tri.add(x,t);
	}
};

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	int Q;
	cin>>Q;

	vector<node> tr(1);
	vector<int> res(Q,-1);

	rep(i,0,Q) {
		string s;
		int a,b;
		cin>>s>>a>>b;
		if (s=="Add") {
			a--;
			int v=sz(tr);
			tr[a].adj.push_back(v);
			tr.emplace_back(tr[a].xum^b,i+1);
		} else {
			a--, b--;
			tr[b].que.emplace_back(tr[a].xum,i+1);
		}
	}

	function<void(int)> dfs=[&](int v) {
		fore(tr[v].adj,u) {
			dfs(u);
			tr[v].tri.merge(tr[u].tri);
		}

		fore(tr[v].que,q) {
			int x,t;
			tie(x,t)=q;
			res[t-1]=tr[v].tri.getmax(x,t);
		}
	};

	dfs(0);

	fore(res,i) if (i!=-1) cout<<i<<'\n';
}

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