oj.uz

답안 #198922

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198922 2020-01-28T06:22:55 Z dimash241 Klasika (COCI20_klasika) C++17
33 / 110
 5000 ms 349296 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 = 30;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 56824 KB Output is correct
2 Correct 42 ms 56800 KB Output is correct
3 Correct 44 ms 56952 KB Output is correct
4 Correct 43 ms 56956 KB Output is correct
5 Correct 42 ms 56824 KB Output is correct
6 Correct 44 ms 56824 KB Output is correct
7 Correct 43 ms 56824 KB Output is correct
8 Correct 43 ms 56996 KB Output is correct
9 Correct 43 ms 56824 KB Output is correct
10 Correct 45 ms 56824 KB Output is correct
11 Correct 45 ms 56952 KB Output is correct
12 Correct 43 ms 56952 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 56824 KB Output is correct
2 Correct 42 ms 56800 KB Output is correct
3 Correct 44 ms 56952 KB Output is correct
4 Correct 43 ms 56956 KB Output is correct
5 Correct 42 ms 56824 KB Output is correct
6 Correct 44 ms 56824 KB Output is correct
7 Correct 43 ms 56824 KB Output is correct
8 Correct 43 ms 56996 KB Output is correct
9 Correct 43 ms 56824 KB Output is correct
10 Correct 45 ms 56824 KB Output is correct
11 Correct 45 ms 56952 KB Output is correct
12 Correct 43 ms 56952 KB Output is correct
13 Correct 44 ms 57340 KB Output is correct
14 Correct 46 ms 57792 KB Output is correct
15 Correct 45 ms 58044 KB Output is correct
16 Correct 48 ms 58616 KB Output is correct
17 Correct 45 ms 57464 KB Output is correct
18 Correct 50 ms 58104 KB Output is correct
19 Correct 51 ms 58676 KB Output is correct
20 Correct 50 ms 59188 KB Output is correct
21 Correct 47 ms 57336 KB Output is correct
22 Correct 47 ms 57976 KB Output is correct
23 Correct 47 ms 58252 KB Output is correct
24 Correct 47 ms 58676 KB Output is correct

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 269 ms 96212 KB Output is correct
2 Correct 363 ms 130764 KB Output is correct
3 Correct 409 ms 152908 KB Output is correct
4 Correct 510 ms 201128 KB Output is correct
5 Correct 429 ms 134164 KB Output is correct
6 Correct 664 ms 208692 KB Output is correct
7 Correct 4531 ms 281260 KB Output is correct
8 Execution timed out 5219 ms 349296 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 56824 KB Output is correct
2 Correct 42 ms 56800 KB Output is correct
3 Correct 44 ms 56952 KB Output is correct
4 Correct 43 ms 56956 KB Output is correct
5 Correct 42 ms 56824 KB Output is correct
6 Correct 44 ms 56824 KB Output is correct
7 Correct 43 ms 56824 KB Output is correct
8 Correct 43 ms 56996 KB Output is correct
9 Correct 43 ms 56824 KB Output is correct
10 Correct 45 ms 56824 KB Output is correct
11 Correct 45 ms 56952 KB Output is correct
12 Correct 43 ms 56952 KB Output is correct
13 Correct 44 ms 57340 KB Output is correct
14 Correct 46 ms 57792 KB Output is correct
15 Correct 45 ms 58044 KB Output is correct
16 Correct 48 ms 58616 KB Output is correct
17 Correct 45 ms 57464 KB Output is correct
18 Correct 50 ms 58104 KB Output is correct
19 Correct 51 ms 58676 KB Output is correct
20 Correct 50 ms 59188 KB Output is correct
21 Correct 47 ms 57336 KB Output is correct
22 Correct 47 ms 57976 KB Output is correct
23 Correct 47 ms 58252 KB Output is correct
24 Correct 47 ms 58676 KB Output is correct
25 Correct 269 ms 96212 KB Output is correct
26 Correct 363 ms 130764 KB Output is correct
27 Correct 409 ms 152908 KB Output is correct
28 Correct 510 ms 201128 KB Output is correct
29 Correct 429 ms 134164 KB Output is correct
30 Correct 664 ms 208692 KB Output is correct
31 Correct 4531 ms 281260 KB Output is correct
32 Execution timed out 5219 ms 349296 KB Time limit exceeded
33 Halted 0 ms 0 KB -