oj.uz

Submission #198410

# Submission time Handle Problem Language Result Execution time Memory
198410 2020-01-26T00:04:15 Z ZwariowanyMarcin Klasika (COCI20_klasika) C++14
0 / 110
 550 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(30 * N + 1, 0);
		go[1].resize(30 * N + 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++;
			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:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &q);
  ~~~~~~^~~~~~~~~~
klasika.cpp:107: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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 486 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 486 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 550 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 486 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -