oj.uz

Submission #291241

# Submission time Handle Problem Language Result Execution time Memory
291241 2020-09-04T23:34:46 Z penguinhacker Klasika (COCI20_klasika) C++17
11 / 110
 5000 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int MAXDIG=30;
struct Node {
	int cnt=0;
	int nxt[2];
	Node() {nxt[0]=nxt[1]=-1;}
};
struct Trie {
	vector<Node> trie;
	Trie() {trie.emplace_back();}
	void reset() {trie.clear(); trie.emplace_back();}
	void add(int x) {
		int cur=0;
		++trie[0].cnt;
		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].cnt;
		}
	}

	/*void remove(int x) {
		int cur=0;
		--trie[0].cnt;
		for (int i=MAXDIG; ~i; --i) {
			int c=(x>>i)&1;
			assert(trie[cur].nxt[c]!=-1);
			cur=trie[cur].nxt[c];
			--trie[cur].cnt;
		}
	}*/

	int qry(int x) { //best xor in trie 
		int cur=0;
		int res=0;
		for (int i=MAXDIG; ~i; --i) {
			int c=(x>>i)&1;
			if (trie[cur].nxt[c^1]!=-1&&trie[trie[cur].nxt[c^1]].cnt>0) {
				res+=(1<<i);
				cur=trie[cur].nxt[c^1];
			}
			else {
				cur=trie[cur].nxt[c];
			}
		}
		return res;
	}
};

//try to rebuild every sqrt(n) queries, change block size to pass constraints
const int mxN=2e5;
int totNodes=1, n, val[mxN], parent[mxN];
int pos[mxN], iPos[mxN], sz[mxN], tin[mxN], tout[mxN];
bool vis[mxN];
vector<int> adj[mxN];
Trie tree[4*mxN];

void dfs(int u, int& ind, int& timer) {
	pos[u]=ind++;
	iPos[pos[u]]=u;
	tin[u]=timer++;
	sz[u]=1;
	for (int v : adj[u]) {
		dfs(v, ind, timer);
		sz[u]+=sz[v];
	}
	tout[u]=timer++;
}

void buildTree(int u=1, int l=0, int r=n-1) { //takes n*log(n)*31 time around
	tree[u].reset();
	for (int i=l; i<=r; ++i) {
		tree[u].add(val[iPos[i]]);
	}
	if (l==r) return;
	int mid=(l+r)/2;
	buildTree(2*u, l, mid), buildTree(2*u+1, mid+1, r);
}

int qry(int ql, int qr, int x, int u=1, int l=0, int r=n-1) { //take log(n)*31 time around
	if (l>qr||r<ql) return 0;
	if (ql<=l&&r<=qr) return tree[u].qry(x);
	int mid=(l+r)/2;
	return max(qry(ql, qr, x, 2*u, l, mid), qry(ql, qr, x, 2*u+1, mid+1, r));
}

vector<int> toCheck;
void rebuild() {
	n=totNodes;
	int ind=0, timer=0;
	dfs(0, ind, timer);
	buildTree();
	for (int i: toCheck) vis[i]=1;
	toCheck.clear();
}

int brute(int u, int x) {
	int res=x^val[u];
	for (int v: adj[u]) res=max(res, brute(v, x));
	return res;
}

int temp[mxN];

int dfs_check(int b, int x) {
	if (vis[x]) {
		return tin[b]<=tin[x]&&tout[b]>=tout[x];
	}
	return temp[x]=dfs_check(b, parent[x]);
}

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

	fill(temp, temp+mxN, -1);
	int q; cin >> q;
	while(q--) {
		string type; cin >> type;
		int a, b; cin >> a >> b;
		if (type=="Add") {
			--a;
			val[totNodes]=val[a]^b;
			adj[a].push_back(totNodes);
			parent[totNodes]=a;
			toCheck.push_back(totNodes);
			++totNodes;
			//rebuild();
			if (totNodes%100==0) rebuild();
		}
		if (type=="Query") {
			--a, --b;
			int ans=0;
			if (vis[b]) {
				int l=pos[b], r=pos[b]+sz[b]-1;
				ans=qry(l, r, val[a]);
				for (int i: toCheck) {
					if (temp[i]==-1) dfs_check(b, i);
					if (temp[i]) {
						ans=max(ans, val[i]^val[a]);
					}
				}
				for (int i: toCheck) temp[i]=-1;
			}
			else {
				ans=brute(b, val[a]);
			}
			cout << ans << "\n";
			//cout << "testing\n";
		}
	}
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 49784 KB Output is correct
2 Correct 61 ms 49600 KB Output is correct
3 Correct 70 ms 50044 KB Output is correct
4 Correct 69 ms 50040 KB Output is correct
5 Correct 61 ms 49656 KB Output is correct
6 Correct 61 ms 49668 KB Output is correct
7 Correct 70 ms 50040 KB Output is correct
8 Correct 72 ms 50076 KB Output is correct
9 Correct 61 ms 49692 KB Output is correct
10 Correct 61 ms 49656 KB Output is correct
11 Correct 69 ms 50088 KB Output is correct
12 Correct 71 ms 50040 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 49784 KB Output is correct
2 Correct 61 ms 49600 KB Output is correct
3 Correct 70 ms 50044 KB Output is correct
4 Correct 69 ms 50040 KB Output is correct
5 Correct 61 ms 49656 KB Output is correct
6 Correct 61 ms 49668 KB Output is correct
7 Correct 70 ms 50040 KB Output is correct
8 Correct 72 ms 50076 KB Output is correct
9 Correct 61 ms 49692 KB Output is correct
10 Correct 61 ms 49656 KB Output is correct
11 Correct 69 ms 50088 KB Output is correct
12 Correct 71 ms 50040 KB Output is correct
13 Correct 84 ms 51448 KB Output is correct
14 Correct 94 ms 53300 KB Output is correct
15 Correct 110 ms 54836 KB Output is correct
16 Correct 128 ms 57520 KB Output is correct
17 Runtime error 347 ms 524288 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5056 ms 106452 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 49784 KB Output is correct
2 Correct 61 ms 49600 KB Output is correct
3 Correct 70 ms 50044 KB Output is correct
4 Correct 69 ms 50040 KB Output is correct
5 Correct 61 ms 49656 KB Output is correct
6 Correct 61 ms 49668 KB Output is correct
7 Correct 70 ms 50040 KB Output is correct
8 Correct 72 ms 50076 KB Output is correct
9 Correct 61 ms 49692 KB Output is correct
10 Correct 61 ms 49656 KB Output is correct
11 Correct 69 ms 50088 KB Output is correct
12 Correct 71 ms 50040 KB Output is correct
13 Correct 84 ms 51448 KB Output is correct
14 Correct 94 ms 53300 KB Output is correct
15 Correct 110 ms 54836 KB Output is correct
16 Correct 128 ms 57520 KB Output is correct
17 Runtime error 347 ms 524288 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -