oj.uz

Submission #339998

# Submission time Handle Problem Language Result Execution time Memory
339998 2020-12-26T14:39:22 Z sinamhdv Klasika (COCI20_klasika) C++11
33 / 110
 2616 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
const ll LINF = (ll)INF * INF;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define msub(a, b) ((mod + ((a) - (b)) % mod) % mod)
#define mdiv(a, b) ((a) * poww((b), mod - 2) % mod)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

struct QR
{
	char op;
	int x, y;
};

#define MAXN 200100
#define LOGN 31
#define MAXL (LOGN * MAXN)

int n, q;
int dp[MAXN];
vector<pii> cld[MAXN];
QR qr[MAXN];
int sttime[MAXN], fntime[MAXN], timer;

inline void getnum(int x, string &bin)
{
	FOR(i, 0, LOGN)
	{
		if (x & (1 << i))
			bin += '1';
		else
			bin += '0';
	}
	reverse(all(bin));
}

void dfs(int v, int x)
{
	sttime[v] = timer++;
	dp[v] = x;
	for (pii p : cld[v])
	{
		dfs(p.fr, x ^ p.sc);
	}
	fntime[v] = timer;
}

int trie[MAXL][2];
set<int> ts[MAXL];
int tn = 1;

inline bool hasrng(int i, int l, int r)
{
	return ts[i].lower_bound(l) != ts[i].upper_bound(r);
}

void add(int i, int x)
{
	string s;
	getnum(x, s);
	int v = 1;
	for (char c : s)
	{
		if (!trie[v][c - '0'])
		{
			tn++;
			trie[v][c - '0'] = tn;
		}
		ts[v].insert(i);
		v = trie[v][c - '0'];
	}
	ts[v].insert(i);
}

int query(int l, int r, int x)
{
	int res = 0;
	string s;
	getnum(x, s);
	int v = 1;
	int bpos = LOGN - 1;
	for (char c : s)
	{
		int b = c - '0';
		if (trie[v][1 - b] && hasrng(trie[v][1 - b], l, r))
		{
			res |= ((1 - b) << bpos);
			v = trie[v][1 - b];
		}
		else
		{
			v = trie[v][b];
			res |= (b << bpos);
		}
		bpos--;
	}
	return res ^ x;
}

int32_t main(void)
{
	fast_io;
	n = 1;
	cin >> q;
	FOR(i, 0, q)
	{
		string op;
		int x, y;
		cin >> op >> x >> y;
		qr[i] = {op[0], x, y};
		if (op[0] == 'A')
		{
			n++;
			cld[x].pb(mp(n, y));
		}
	}
	dfs(1, 0);
	
	int cnt = 1;
	add(sttime[1], dp[1]);
	FOR(i, 0, q)
	{
		if (qr[i].op == 'A')
		{
			cnt++;
			add(sttime[cnt], dp[cnt]);
		}
		else
		{
			cout << query(sttime[qr[i].y], fntime[qr[i].y] - 1, dp[qr[i].x]) << endl;
		}
	}
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 296676 KB Output is correct
2 Correct 186 ms 296684 KB Output is correct
3 Correct 182 ms 296684 KB Output is correct
4 Correct 186 ms 296684 KB Output is correct
5 Correct 183 ms 296556 KB Output is correct
6 Correct 183 ms 296556 KB Output is correct
7 Correct 184 ms 296684 KB Output is correct
8 Correct 185 ms 296684 KB Output is correct
9 Correct 182 ms 296556 KB Output is correct
10 Correct 183 ms 296684 KB Output is correct
11 Correct 181 ms 296684 KB Output is correct
12 Correct 187 ms 296668 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 296676 KB Output is correct
2 Correct 186 ms 296684 KB Output is correct
3 Correct 182 ms 296684 KB Output is correct
4 Correct 186 ms 296684 KB Output is correct
5 Correct 183 ms 296556 KB Output is correct
6 Correct 183 ms 296556 KB Output is correct
7 Correct 184 ms 296684 KB Output is correct
8 Correct 185 ms 296684 KB Output is correct
9 Correct 182 ms 296556 KB Output is correct
10 Correct 183 ms 296684 KB Output is correct
11 Correct 181 ms 296684 KB Output is correct
12 Correct 187 ms 296668 KB Output is correct
13 Correct 189 ms 297168 KB Output is correct
14 Correct 190 ms 298100 KB Output is correct
15 Correct 189 ms 298604 KB Output is correct
16 Correct 191 ms 299244 KB Output is correct
17 Correct 187 ms 297324 KB Output is correct
18 Correct 190 ms 297964 KB Output is correct
19 Correct 190 ms 298604 KB Output is correct
20 Correct 195 ms 299264 KB Output is correct
21 Correct 188 ms 297196 KB Output is correct
22 Correct 188 ms 297836 KB Output is correct
23 Correct 193 ms 298604 KB Output is correct
24 Correct 191 ms 299372 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1488 ms 370924 KB Output is correct
2 Correct 2147 ms 440028 KB Output is correct
3 Correct 2616 ms 506860 KB Output is correct
4 Runtime error 2119 ms 524288 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 195 ms 296676 KB Output is correct
2 Correct 186 ms 296684 KB Output is correct
3 Correct 182 ms 296684 KB Output is correct
4 Correct 186 ms 296684 KB Output is correct
5 Correct 183 ms 296556 KB Output is correct
6 Correct 183 ms 296556 KB Output is correct
7 Correct 184 ms 296684 KB Output is correct
8 Correct 185 ms 296684 KB Output is correct
9 Correct 182 ms 296556 KB Output is correct
10 Correct 183 ms 296684 KB Output is correct
11 Correct 181 ms 296684 KB Output is correct
12 Correct 187 ms 296668 KB Output is correct
13 Correct 189 ms 297168 KB Output is correct
14 Correct 190 ms 298100 KB Output is correct
15 Correct 189 ms 298604 KB Output is correct
16 Correct 191 ms 299244 KB Output is correct
17 Correct 187 ms 297324 KB Output is correct
18 Correct 190 ms 297964 KB Output is correct
19 Correct 190 ms 298604 KB Output is correct
20 Correct 195 ms 299264 KB Output is correct
21 Correct 188 ms 297196 KB Output is correct
22 Correct 188 ms 297836 KB Output is correct
23 Correct 193 ms 298604 KB Output is correct
24 Correct 191 ms 299372 KB Output is correct
25 Correct 1488 ms 370924 KB Output is correct
26 Correct 2147 ms 440028 KB Output is correct
27 Correct 2616 ms 506860 KB Output is correct
28 Runtime error 2119 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -