oj.uz

Submission #198499

# Submission time Handle Problem Language Result Execution time Memory
198499 2020-01-26T12:02:02 Z ZwariowanyMarcin Klasika (COCI20_klasika) C++14
33 / 110
 3356 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);
const int N = 6000100;

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];
	set <int> s[N];
	
	void init() {
		for (int i = 0; i < 2; ++i)
			go[i].resize(N, 0);
	}
	
	void add(const int& nr, const 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++;
			u = go[c][u];
			s[u].insert(nr);
		}
	}
	
	int query(int L, int R, const int& x) {
		int res = 0;
		int u = 0;
		for (int i = 29; 0 <= i; --i) {
			int c = !((x >> i) & 1);
			if (go[c][u] && s[go[c][u]].lower_bound(L) != s[go[c][u]].end() && *s[go[c][u]].lower_bound(L) <= R) {
				res += 1 << i;
				u = go[c][u];
			}
			else
				u = go[!c][u];
			if (!u) return 0;
		}
		return res;
	}
} ja;

int main() {
	ja.init();
	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);

	ja.add(in[1], 0);
	
	for (int i = 1; i <= q; ++i) {
		if (t[i] == 1) ja.add(in[e[i]], path[e[i]]);
		else printf ("%d\n", ja.query(in[b[i]], out[b[i]] - 1, path[a[i]]));
	} 
		
	return 0;
}

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &q);
  ~~~~~~^~~~~~~~~~
klasika.cpp:85: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 223 ms 334004 KB Output is correct
2 Correct 193 ms 333944 KB Output is correct
3 Correct 188 ms 334076 KB Output is correct
4 Correct 194 ms 334072 KB Output is correct
5 Correct 190 ms 333944 KB Output is correct
6 Correct 190 ms 334068 KB Output is correct
7 Correct 194 ms 334072 KB Output is correct
8 Correct 189 ms 334200 KB Output is correct
9 Correct 188 ms 334072 KB Output is correct
10 Correct 196 ms 334072 KB Output is correct
11 Correct 191 ms 334072 KB Output is correct
12 Correct 192 ms 334176 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 334004 KB Output is correct
2 Correct 193 ms 333944 KB Output is correct
3 Correct 188 ms 334076 KB Output is correct
4 Correct 194 ms 334072 KB Output is correct
5 Correct 190 ms 333944 KB Output is correct
6 Correct 190 ms 334068 KB Output is correct
7 Correct 194 ms 334072 KB Output is correct
8 Correct 189 ms 334200 KB Output is correct
9 Correct 188 ms 334072 KB Output is correct
10 Correct 196 ms 334072 KB Output is correct
11 Correct 191 ms 334072 KB Output is correct
12 Correct 192 ms 334176 KB Output is correct
13 Correct 195 ms 334456 KB Output is correct
14 Correct 201 ms 335096 KB Output is correct
15 Correct 197 ms 335736 KB Output is correct
16 Correct 201 ms 336440 KB Output is correct
17 Correct 198 ms 334452 KB Output is correct
18 Correct 198 ms 334968 KB Output is correct
19 Correct 200 ms 335608 KB Output is correct
20 Correct 202 ms 336248 KB Output is correct
21 Correct 195 ms 334456 KB Output is correct
22 Correct 197 ms 335096 KB Output is correct
23 Correct 202 ms 335736 KB Output is correct
24 Correct 204 ms 336120 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1263 ms 397768 KB Output is correct
2 Correct 1983 ms 456956 KB Output is correct
3 Correct 3356 ms 515432 KB Output is correct
4 Runtime error 2616 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 223 ms 334004 KB Output is correct
2 Correct 193 ms 333944 KB Output is correct
3 Correct 188 ms 334076 KB Output is correct
4 Correct 194 ms 334072 KB Output is correct
5 Correct 190 ms 333944 KB Output is correct
6 Correct 190 ms 334068 KB Output is correct
7 Correct 194 ms 334072 KB Output is correct
8 Correct 189 ms 334200 KB Output is correct
9 Correct 188 ms 334072 KB Output is correct
10 Correct 196 ms 334072 KB Output is correct
11 Correct 191 ms 334072 KB Output is correct
12 Correct 192 ms 334176 KB Output is correct
13 Correct 195 ms 334456 KB Output is correct
14 Correct 201 ms 335096 KB Output is correct
15 Correct 197 ms 335736 KB Output is correct
16 Correct 201 ms 336440 KB Output is correct
17 Correct 198 ms 334452 KB Output is correct
18 Correct 198 ms 334968 KB Output is correct
19 Correct 200 ms 335608 KB Output is correct
20 Correct 202 ms 336248 KB Output is correct
21 Correct 195 ms 334456 KB Output is correct
22 Correct 197 ms 335096 KB Output is correct
23 Correct 202 ms 335736 KB Output is correct
24 Correct 204 ms 336120 KB Output is correct
25 Correct 1263 ms 397768 KB Output is correct
26 Correct 1983 ms 456956 KB Output is correct
27 Correct 3356 ms 515432 KB Output is correct
28 Runtime error 2616 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -