oj.uz

Submission #198412

# Submission time Handle Problem Language Result Execution time Memory
198412 2020-01-26T00:20:32 Z ZwariowanyMarcin Klasika (COCI20_klasika) C++14
33 / 110
 2587 ms 524292 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define LL long long
#define ld long double
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define boost cin.tie(0), ios_base::sync_with_stdio(0);


using namespace std;		

const int nax = 200100;
const int pod = (1 << 18);

int q;
int t[nax];
int a[nax];
int b[nax];
int e[nax];

char s[10];

vector <int> v[nax];
int path[nax];

int tim;
int in[nax];
int out[nax];

void dfs(int u) {
	in[u] = tim++;
	for (auto it : v[u])
		dfs(it);
	out[u] = tim;
}

struct trie {
	int fre = 1;
	vector <int> go[2];
	
	void init(int N) {
		go[0].resize(1, 0);
		go[1].resize(1, 0);
	}
	
	void add(int x) {
		int u = 0;
		for (int i = 29; 0 <= i; --i) {
			int c = ((x >> i) & 1);
			if (!go[c][u]) {
				go[c][u] = fre++;
				go[0].pb(0);
				go[1].pb(0);
			}
			u = go[c][u];
		}
	}
	
	int query(int x) {
		int res = 0;
		int u = 0;
		for (int i = 29; 0 <= i; --i) {
			int c = !((x >> i) & 1);
			if (go[c][u]) {
				res += 1LL << i;
				u = go[c][u];
			}
			else if(go[!c][u]) 
				u = go[!c][u];
			else return 0;
		}
		return res;
	}
};

trie d[2 * pod];
				
void add(int u, int x) {
	u += pod;
	while (u) {
		d[u].add(x);
		u /= 2;
	}
}	

void make(int u = 1, int z = pod) {
	d[u].init(z);
	if (pod <= u) return;
	make(2 * u, z / 2);
	make(2 * u + 1, z / 2);
}		

int query(int x, int y, int z, int u = 1, int l = 0, int r = pod - 1) {
	if (x <= l && r <= y) 
		return d[u].query(z);
	int res = 0;
	int m = (l + r) / 2;
	if (x <= m) res = query(x, y, z, 2 * u, l, m);
	if (m < y) res = max(res, query(x, y, z, 2 * u + 1, m + 1, r));
	return res;
}

int main() {
	scanf ("%d", &q);
	int node = 2;
	for (int i = 1; i <= q; ++i) {
		scanf ("%s%d%d", s, a + i, b + i);
		t[i] = (s[0] == 'A');
		if (t[i]) {
			e[i] = node;
			path[node] = (path[a[i]] ^ b[i]);
			v[a[i]].pb(node++);
		}
	}
	dfs(1);
	
	make();
	
	add(in[1], 0);
	for (int i = 1; i <= q; ++i) {
		if (t[i] == 1) add(in[e[i]], path[e[i]]);
		else printf ("%d\n", query(in[b[i]], out[b[i]] - 1, path[a[i]]));
	} 
		
	return 0;
}

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &q);
  ~~~~~~^~~~~~~~~~
klasika.cpp:111:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%s%d%d", s, a + i, b + i);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 67192 KB Output is correct
2 Correct 168 ms 66912 KB Output is correct
3 Correct 173 ms 67268 KB Output is correct
4 Correct 184 ms 67332 KB Output is correct
5 Correct 165 ms 66836 KB Output is correct
6 Correct 167 ms 66876 KB Output is correct
7 Correct 172 ms 67196 KB Output is correct
8 Correct 204 ms 67344 KB Output is correct
9 Correct 216 ms 67068 KB Output is correct
10 Correct 168 ms 67416 KB Output is correct
11 Correct 162 ms 67396 KB Output is correct
12 Correct 172 ms 67288 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 67192 KB Output is correct
2 Correct 168 ms 66912 KB Output is correct
3 Correct 173 ms 67268 KB Output is correct
4 Correct 184 ms 67332 KB Output is correct
5 Correct 165 ms 66836 KB Output is correct
6 Correct 167 ms 66876 KB Output is correct
7 Correct 172 ms 67196 KB Output is correct
8 Correct 204 ms 67344 KB Output is correct
9 Correct 216 ms 67068 KB Output is correct
10 Correct 168 ms 67416 KB Output is correct
11 Correct 162 ms 67396 KB Output is correct
12 Correct 172 ms 67288 KB Output is correct
13 Correct 209 ms 68776 KB Output is correct
14 Correct 179 ms 70524 KB Output is correct
15 Correct 189 ms 71880 KB Output is correct
16 Correct 192 ms 73820 KB Output is correct
17 Correct 186 ms 68640 KB Output is correct
18 Correct 177 ms 70520 KB Output is correct
19 Correct 202 ms 71992 KB Output is correct
20 Correct 188 ms 72888 KB Output is correct
21 Correct 169 ms 68728 KB Output is correct
22 Correct 211 ms 70648 KB Output is correct
23 Correct 225 ms 71672 KB Output is correct
24 Correct 192 ms 72952 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1116 ms 224548 KB Output is correct
2 Correct 1821 ms 375780 KB Output is correct
3 Correct 2587 ms 524288 KB Output is correct
4 Runtime error 2368 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 67192 KB Output is correct
2 Correct 168 ms 66912 KB Output is correct
3 Correct 173 ms 67268 KB Output is correct
4 Correct 184 ms 67332 KB Output is correct
5 Correct 165 ms 66836 KB Output is correct
6 Correct 167 ms 66876 KB Output is correct
7 Correct 172 ms 67196 KB Output is correct
8 Correct 204 ms 67344 KB Output is correct
9 Correct 216 ms 67068 KB Output is correct
10 Correct 168 ms 67416 KB Output is correct
11 Correct 162 ms 67396 KB Output is correct
12 Correct 172 ms 67288 KB Output is correct
13 Correct 209 ms 68776 KB Output is correct
14 Correct 179 ms 70524 KB Output is correct
15 Correct 189 ms 71880 KB Output is correct
16 Correct 192 ms 73820 KB Output is correct
17 Correct 186 ms 68640 KB Output is correct
18 Correct 177 ms 70520 KB Output is correct
19 Correct 202 ms 71992 KB Output is correct
20 Correct 188 ms 72888 KB Output is correct
21 Correct 169 ms 68728 KB Output is correct
22 Correct 211 ms 70648 KB Output is correct
23 Correct 225 ms 71672 KB Output is correct
24 Correct 192 ms 72952 KB Output is correct
25 Correct 1116 ms 224548 KB Output is correct
26 Correct 1821 ms 375780 KB Output is correct
27 Correct 2587 ms 524288 KB Output is correct
28 Runtime error 2368 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -