oj.uz

Submission #291268

# Submission time Handle Problem Language Result Execution time Memory
291268 2020-09-05T02:48:19 Z penguinhacker Klasika (COCI20_klasika) C++17
110 / 110
 3059 ms 377464 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

//#warning changenodes
const int MAXDIG=30, MXNODES=7e6;
struct Node {
	int nxt[2];
	set<int> pos;
	Node() {nxt[0]=nxt[1]=-1;}
};
struct Trie {
	vector<Node> trie;
	Trie() {trie.reserve(MXNODES); trie.emplace_back();}
	void add(int x, int p) {
		int cur=0;
		for (int i=MAXDIG; ~i; --i) {
			int c=(x>>i)&1;
			if (trie[cur].nxt[c]==-1) {
				trie[cur].nxt[c]=trie.size();
				trie.emplace_back();
			}
			cur=trie[cur].nxt[c];
			trie[cur].pos.insert(p);
		}
	}

	int qry(int x, int ql, int qr) { //best xor in trie 
		int cur=0;
		int res=0;
		for (int i=MAXDIG; ~i; --i) {
			int c=(x>>i)&1;
			int chk=trie[cur].nxt[c^1];
			bool can=chk!=-1;
			if (can) {
				auto it=trie[chk].pos.lower_bound(ql);
				if (it==trie[chk].pos.end()||*it>qr) can=0;
			}
			if (can) {
				res+=(1<<i);
				cur=chk;
			}
			else {
				cur=trie[cur].nxt[c];
			}
		}
		return res;
	}
} t;

const int mxN=2e5;
int n=1, q, val[mxN], which[mxN];
int tin[mxN], tout[mxN], timer=0;
ar<int, 3> queries[mxN];
vector<int> adj[mxN];

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

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

	cin >> q;
	for (int i=0; i<q; ++i) {
		string s; cin >> s;
		int type=s=="Add"?1:2;
		int a, b; cin >> a >> b;
		if (type==1) {
			--a;
			adj[a].push_back(n);
			val[n]=val[a]^b;
			b=val[n];
			a=n++;
		}
		else --a, --b;
		queries[i]={type, a, b};
	}
	//for (int i=0; i<n; ++i) cout << val[i] << " ";
	dfs();
	t.add(0, 0);
	for (int i=0; i<q; ++i) {
		int a=queries[i][1], b=queries[i][2];
		if (queries[i][0]==1) {
			t.add(b, tin[a]);
		}
		else { //b
			int ans=t.qry(val[a], tin[b], tout[b]);
			cout << ans << "\n";
		}
	}
	/*while(q--) {
		string type; cin >> type;
		int a, b; cin >> a >> b;
		if (type=="Add") {
			--a;
			val[n]=val[a]^b;
			adj[a].push_back(n);
			trie.add(val[n]);
			++n;
		}
		if (type=="Query") {
			--a, --b;
			int ans=q<=2000?dfs(b, val[a]):trie.qry(val[a]);
			cout << ans << "\n";
		}
	}*/
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5248 KB Output is correct
2 Correct 4 ms 5248 KB Output is correct
3 Correct 4 ms 5504 KB Output is correct
4 Correct 4 ms 5504 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 4 ms 5376 KB Output is correct
7 Correct 4 ms 5504 KB Output is correct
8 Correct 4 ms 5632 KB Output is correct
9 Correct 4 ms 5248 KB Output is correct
10 Correct 4 ms 5376 KB Output is correct
11 Correct 4 ms 5376 KB Output is correct
12 Correct 4 ms 5504 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5248 KB Output is correct
2 Correct 4 ms 5248 KB Output is correct
3 Correct 4 ms 5504 KB Output is correct
4 Correct 4 ms 5504 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 4 ms 5376 KB Output is correct
7 Correct 4 ms 5504 KB Output is correct
8 Correct 4 ms 5632 KB Output is correct
9 Correct 4 ms 5248 KB Output is correct
10 Correct 4 ms 5376 KB Output is correct
11 Correct 4 ms 5376 KB Output is correct
12 Correct 4 ms 5504 KB Output is correct
13 Correct 7 ms 6272 KB Output is correct
14 Correct 8 ms 7296 KB Output is correct
15 Correct 10 ms 8448 KB Output is correct
16 Correct 12 ms 9344 KB Output is correct
17 Correct 7 ms 6144 KB Output is correct
18 Correct 9 ms 7296 KB Output is correct
19 Correct 11 ms 8320 KB Output is correct
20 Correct 12 ms 9216 KB Output is correct
21 Correct 7 ms 6144 KB Output is correct
22 Correct 9 ms 7296 KB Output is correct
23 Correct 10 ms 8320 KB Output is correct
24 Correct 12 ms 9216 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 104696 KB Output is correct
2 Correct 1440 ms 196288 KB Output is correct
3 Correct 2005 ms 284712 KB Output is correct
4 Correct 2647 ms 373428 KB Output is correct
5 Correct 852 ms 103032 KB Output is correct
6 Correct 1544 ms 193016 KB Output is correct
7 Correct 2165 ms 279708 KB Output is correct
8 Correct 2828 ms 366604 KB Output is correct
9 Correct 848 ms 102776 KB Output is correct
10 Correct 1474 ms 193784 KB Output is correct
11 Correct 2110 ms 281840 KB Output is correct
12 Correct 2752 ms 368484 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5248 KB Output is correct
2 Correct 4 ms 5248 KB Output is correct
3 Correct 4 ms 5504 KB Output is correct
4 Correct 4 ms 5504 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 4 ms 5376 KB Output is correct
7 Correct 4 ms 5504 KB Output is correct
8 Correct 4 ms 5632 KB Output is correct
9 Correct 4 ms 5248 KB Output is correct
10 Correct 4 ms 5376 KB Output is correct
11 Correct 4 ms 5376 KB Output is correct
12 Correct 4 ms 5504 KB Output is correct
13 Correct 7 ms 6272 KB Output is correct
14 Correct 8 ms 7296 KB Output is correct
15 Correct 10 ms 8448 KB Output is correct
16 Correct 12 ms 9344 KB Output is correct
17 Correct 7 ms 6144 KB Output is correct
18 Correct 9 ms 7296 KB Output is correct
19 Correct 11 ms 8320 KB Output is correct
20 Correct 12 ms 9216 KB Output is correct
21 Correct 7 ms 6144 KB Output is correct
22 Correct 9 ms 7296 KB Output is correct
23 Correct 10 ms 8320 KB Output is correct
24 Correct 12 ms 9216 KB Output is correct
25 Correct 802 ms 104696 KB Output is correct
26 Correct 1440 ms 196288 KB Output is correct
27 Correct 2005 ms 284712 KB Output is correct
28 Correct 2647 ms 373428 KB Output is correct
29 Correct 852 ms 103032 KB Output is correct
30 Correct 1544 ms 193016 KB Output is correct
31 Correct 2165 ms 279708 KB Output is correct
32 Correct 2828 ms 366604 KB Output is correct
33 Correct 848 ms 102776 KB Output is correct
34 Correct 1474 ms 193784 KB Output is correct
35 Correct 2110 ms 281840 KB Output is correct
36 Correct 2752 ms 368484 KB Output is correct
37 Correct 1409 ms 105208 KB Output is correct
38 Correct 2029 ms 199544 KB Output is correct
39 Correct 2483 ms 290220 KB Output is correct
40 Correct 2852 ms 377464 KB Output is correct
41 Correct 1531 ms 106360 KB Output is correct
42 Correct 2138 ms 196124 KB Output is correct
43 Correct 2635 ms 283256 KB Output is correct
44 Correct 3059 ms 369792 KB Output is correct
45 Correct 1614 ms 106260 KB Output is correct
46 Correct 2286 ms 197240 KB Output is correct
47 Correct 2695 ms 284236 KB Output is correct
48 Correct 3031 ms 372184 KB Output is correct