oj.uz

Submission #198923

# Submission time Handle Problem Language Result Execution time Memory
198923 2020-01-28T06:24:06 Z dimash241 Klasika (COCI20_klasika) C++17
110 / 110
 1591 ms 373756 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("O3")

# include <x86intrin.h>
# include <bits/stdc++.h>

# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
 
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red
 
inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}
 
const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 8e6 + 9;
const int N = 6e5 + 3;                                          
const int M = 22;
const int K = 29;
const int pri = 997;
const int Magic = 2101;
 
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
 
int n = 1;
int ans[N];
int pref[N];
int Query[N];
vector < pair < int, int > > g[N], qb[N];
int f[N];
 
#define trie bor
struct trie {
	int to[2];
	int mn;
	trie () {
		to[0] = to[1] = 0;
		mn = inf;
	}
};

vector < trie > t[N];
vector < int > sub[N];
int p[N];
 
inline void upd (int rt, int val, int id) {
	int v = 0;
//	cout << "root: " << rt << '\n';
//	cout << rt << ' ' << val << ' ' << id << '\n';
	for (int i = K; i >= 0; i --) {
    	int bit = ((val >> i) & 1);
    	
		if (!t[rt][v].to[bit]) {
			t[rt][v].to[bit] = sz(t[rt]);
			t[rt].pb(trie());
		}
		t[rt][v].mn = min(t[rt][v].mn, id);
		//cout << v << ' ' << t[rt][v].to[bit] << '\n';
		v = t[rt][v].to[bit];
	}
 
	t[rt][v].mn = min(t[rt][v].mn, id);
}
 
inline int get (int rt, int val, int r) {
	int v = 0;
	int res = 0;
 
	for (int i = K; i >= 0; i --) {
    	int bit = ((val >> i) & 1);
 
		bit ^= 1;
		//cout << bit << ' ' << 
 
//		cout << t[rt][v].to[bit] << ' ' << t[rt][t[rt][v].to[bit]].mn << '\n';
		if (t[rt][v].to[bit] > 0 && t[rt][t[rt][v].to[bit]].mn <= r) {
			res |= (1 << i);
			v = t[rt][v].to[bit];
		} else {
			bit ^= 1;		
			v = t[rt][v].to[bit];
	
		}
	}
//	cout << res << ' ' << t[rt][v].mn << '\n';
	return res;
}
 
void dfs (int v, int pr = 0) {
	//cout << v << ' ' << f[v] << '\n';
	p[v] = v;
 
	for (auto to : g[v]) {
		f[to.F] = (f[v] ^ to.S);
		dfs(to.F);
	}
}
 
void _merge (int v, int to) {
	if (sub[p[v]].size() < sub[p[to]].size()) {
		swap(p[v], p[to]);
	}

	for (auto x : sub[p[to]]) {
		sub[p[v]].pb(x);
		upd (p[v], f[x], x);
	}
}
               	
 
void go (int v, int pr = 0) {
	sub[p[v]].pb(v);
	t[p[v]].pb(trie());
//	cout << "check: " << p[v] << ' ' << f[v] << ' ' << v << '\n';
	upd (p[v], f[v], v);
	for (auto to : g[v]) {
		go(to.F);
		_merge(v, to.F);
	}
	
	for (auto x : qb[v]) {
	//	cout << f[x.S] << ' ' << get(p[v], f[x.S], pref[x.F]) << '\n';
	//	cout << x.F << ":\n";
		ans[x.F] = get(p[v], f[x.S], pref[x.F]);
//		exit(0);
	}
}
 
int main () {
	SpeedForce;
	int m;
	cin >> m;
	for (int i = 1; i <= m; i ++) {
 
		string type;
		cin >> type;
		if (type == "Add") {
			int x, y;
			cin >> x >> y;
			g[x].pb(mp(++n, y));
		} else {
			int a, b;
			cin >> a >> b;
			qb[b].pb(mp(i, a));
			Query[i] = 1;
		}
		
		pref[i] = n;		
	}
	
	dfs(1);
	go(1);
 
	for (int i = 1; i <= m; i++)
		if (Query[i])
			cout << ans[i] << '\n';
 
	return Accepted;
}
 
// B...a

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 56824 KB Output is correct
2 Correct 42 ms 56788 KB Output is correct
3 Correct 42 ms 56824 KB Output is correct
4 Correct 41 ms 56952 KB Output is correct
5 Correct 43 ms 56824 KB Output is correct
6 Correct 44 ms 56824 KB Output is correct
7 Correct 42 ms 56952 KB Output is correct
8 Correct 42 ms 56952 KB Output is correct
9 Correct 43 ms 56824 KB Output is correct
10 Correct 43 ms 56952 KB Output is correct
11 Correct 46 ms 56956 KB Output is correct
12 Correct 42 ms 56952 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 56824 KB Output is correct
2 Correct 42 ms 56788 KB Output is correct
3 Correct 42 ms 56824 KB Output is correct
4 Correct 41 ms 56952 KB Output is correct
5 Correct 43 ms 56824 KB Output is correct
6 Correct 44 ms 56824 KB Output is correct
7 Correct 42 ms 56952 KB Output is correct
8 Correct 42 ms 56952 KB Output is correct
9 Correct 43 ms 56824 KB Output is correct
10 Correct 43 ms 56952 KB Output is correct
11 Correct 46 ms 56956 KB Output is correct
12 Correct 42 ms 56952 KB Output is correct
13 Correct 49 ms 57336 KB Output is correct
14 Correct 44 ms 57792 KB Output is correct
15 Correct 47 ms 58044 KB Output is correct
16 Correct 49 ms 58616 KB Output is correct
17 Correct 47 ms 57464 KB Output is correct
18 Correct 47 ms 58104 KB Output is correct
19 Correct 49 ms 58744 KB Output is correct
20 Correct 49 ms 59188 KB Output is correct
21 Correct 45 ms 57336 KB Output is correct
22 Correct 47 ms 57976 KB Output is correct
23 Correct 48 ms 58232 KB Output is correct
24 Correct 47 ms 58676 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 96212 KB Output is correct
2 Correct 405 ms 130636 KB Output is correct
3 Correct 408 ms 152900 KB Output is correct
4 Correct 480 ms 201264 KB Output is correct
5 Correct 382 ms 134164 KB Output is correct
6 Correct 625 ms 208680 KB Output is correct
7 Correct 887 ms 281216 KB Output is correct
8 Correct 1591 ms 366136 KB Output is correct
9 Correct 312 ms 107556 KB Output is correct
10 Correct 445 ms 156492 KB Output is correct
11 Correct 551 ms 195120 KB Output is correct
12 Correct 681 ms 256304 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 56824 KB Output is correct
2 Correct 42 ms 56788 KB Output is correct
3 Correct 42 ms 56824 KB Output is correct
4 Correct 41 ms 56952 KB Output is correct
5 Correct 43 ms 56824 KB Output is correct
6 Correct 44 ms 56824 KB Output is correct
7 Correct 42 ms 56952 KB Output is correct
8 Correct 42 ms 56952 KB Output is correct
9 Correct 43 ms 56824 KB Output is correct
10 Correct 43 ms 56952 KB Output is correct
11 Correct 46 ms 56956 KB Output is correct
12 Correct 42 ms 56952 KB Output is correct
13 Correct 49 ms 57336 KB Output is correct
14 Correct 44 ms 57792 KB Output is correct
15 Correct 47 ms 58044 KB Output is correct
16 Correct 49 ms 58616 KB Output is correct
17 Correct 47 ms 57464 KB Output is correct
18 Correct 47 ms 58104 KB Output is correct
19 Correct 49 ms 58744 KB Output is correct
20 Correct 49 ms 59188 KB Output is correct
21 Correct 45 ms 57336 KB Output is correct
22 Correct 47 ms 57976 KB Output is correct
23 Correct 48 ms 58232 KB Output is correct
24 Correct 47 ms 58676 KB Output is correct
25 Correct 263 ms 96212 KB Output is correct
26 Correct 405 ms 130636 KB Output is correct
27 Correct 408 ms 152900 KB Output is correct
28 Correct 480 ms 201264 KB Output is correct
29 Correct 382 ms 134164 KB Output is correct
30 Correct 625 ms 208680 KB Output is correct
31 Correct 887 ms 281216 KB Output is correct
32 Correct 1591 ms 366136 KB Output is correct
33 Correct 312 ms 107556 KB Output is correct
34 Correct 445 ms 156492 KB Output is correct
35 Correct 551 ms 195120 KB Output is correct
36 Correct 681 ms 256304 KB Output is correct
37 Correct 328 ms 96604 KB Output is correct
38 Correct 419 ms 132264 KB Output is correct
39 Correct 453 ms 155084 KB Output is correct
40 Correct 504 ms 202808 KB Output is correct
41 Correct 408 ms 136992 KB Output is correct
42 Correct 666 ms 211748 KB Output is correct
43 Correct 878 ms 278324 KB Output is correct
44 Correct 1457 ms 373756 KB Output is correct
45 Correct 336 ms 108820 KB Output is correct
46 Correct 471 ms 157832 KB Output is correct
47 Correct 610 ms 195316 KB Output is correct
48 Correct 677 ms 258284 KB Output is correct