oj.uz

Submission #197995

# Submission time Handle Problem Language Result Execution time Memory
197995 2020-01-24T12:50:31 Z ami Klasika (COCI20_klasika) C++17
110 / 110
 1419 ms 209800 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 528 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 632 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 528 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 5 ms 1144 KB Output is correct
14 Correct 6 ms 1652 KB Output is correct
15 Correct 7 ms 2036 KB Output is correct
16 Correct 8 ms 2796 KB Output is correct
17 Correct 5 ms 1016 KB Output is correct
18 Correct 8 ms 1564 KB Output is correct
19 Correct 10 ms 2016 KB Output is correct
20 Correct 12 ms 2176 KB Output is correct
21 Correct 5 ms 1080 KB Output is correct
22 Correct 7 ms 1484 KB Output is correct
23 Correct 9 ms 2116 KB Output is correct
24 Correct 10 ms 2468 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 54120 KB Output is correct
2 Correct 467 ms 106128 KB Output is correct
3 Correct 572 ms 136660 KB Output is correct
4 Correct 708 ms 209044 KB Output is correct
5 Correct 484 ms 43656 KB Output is correct
6 Correct 813 ms 101936 KB Output is correct
7 Correct 1111 ms 118804 KB Output is correct
8 Correct 1402 ms 179964 KB Output is correct
9 Correct 393 ms 50904 KB Output is correct
10 Correct 579 ms 99384 KB Output is correct
11 Correct 734 ms 133776 KB Output is correct
12 Correct 963 ms 195692 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 528 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 5 ms 1144 KB Output is correct
14 Correct 6 ms 1652 KB Output is correct
15 Correct 7 ms 2036 KB Output is correct
16 Correct 8 ms 2796 KB Output is correct
17 Correct 5 ms 1016 KB Output is correct
18 Correct 8 ms 1564 KB Output is correct
19 Correct 10 ms 2016 KB Output is correct
20 Correct 12 ms 2176 KB Output is correct
21 Correct 5 ms 1080 KB Output is correct
22 Correct 7 ms 1484 KB Output is correct
23 Correct 9 ms 2116 KB Output is correct
24 Correct 10 ms 2468 KB Output is correct
25 Correct 310 ms 54120 KB Output is correct
26 Correct 467 ms 106128 KB Output is correct
27 Correct 572 ms 136660 KB Output is correct
28 Correct 708 ms 209044 KB Output is correct
29 Correct 484 ms 43656 KB Output is correct
30 Correct 813 ms 101936 KB Output is correct
31 Correct 1111 ms 118804 KB Output is correct
32 Correct 1402 ms 179964 KB Output is correct
33 Correct 393 ms 50904 KB Output is correct
34 Correct 579 ms 99384 KB Output is correct
35 Correct 734 ms 133776 KB Output is correct
36 Correct 963 ms 195692 KB Output is correct
37 Correct 377 ms 55224 KB Output is correct
38 Correct 523 ms 106912 KB Output is correct
39 Correct 619 ms 138264 KB Output is correct
40 Correct 736 ms 209800 KB Output is correct
41 Correct 485 ms 52952 KB Output is correct
42 Correct 849 ms 101092 KB Output is correct
43 Correct 1094 ms 129580 KB Output is correct
44 Correct 1419 ms 184580 KB Output is correct
45 Correct 395 ms 53044 KB Output is correct
46 Correct 626 ms 102628 KB Output is correct
47 Correct 760 ms 136020 KB Output is correct
48 Correct 944 ms 198048 KB Output is correct