oj.uz

Submission #868778

# Submission time Handle Problem Language Result Execution time Memory
868778 2023-11-02T02:05:32 Z pcc Klasika (COCI20_klasika) C++14
33 / 110
 3055 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define tiii tuple<int,int,int>


const int mxn = 2e5+10;
const int SZ = mxn*165;
vector<int> tree[mxn];
int arr[mxn],dp[mxn];
pii eul[mxn];
pii trie[SZ];
int segtree[mxn*4];
int ppp = 0;
int C = 0;
tiii req[mxn];

int newnode(){
	assert(++ppp<SZ);
	return ppp;
}
void add(int now,int val){
	for(int i = 30;i>=0;i--){
		if(val&(1<<i)){
			if(!trie[now].sc)trie[now].sc = newnode();
			now = trie[now].sc;
		}
		else{
			if(!trie[now].fs)trie[now].fs = newnode();
			now = trie[now].fs;
		}
	}
	return;
}
int getbig(int now,int tar){
	int re = 0;
	if(!trie[now].fs&&!trie[now].sc)return -1;
	for(int i = 30;i>=0;i--){
		if(tar&(1<<i)){
			if(trie[now].fs)now = trie[now].fs,re^=1<<i;
			else now = trie[now].sc;
		}
		else{
			if(trie[now].sc)now = trie[now].sc,re^=1<<i;
			else now = trie[now].fs;
		}
	}
	return re;
}

void modify(int now,int l,int r,int p,int v){
	if(!segtree[now])segtree[now] = newnode();
	add(segtree[now],v);
	if(l == r)return;
	int mid = (l+r)>>1;
	if(mid>=p)modify(now*2+1,l,mid,p,v);
	else modify(now*2+2,mid+1,r,p,v);
	return;
}
int getans(int now,int l,int r,int s,int e,int tar){
	if(l>=s&&e>=r)return getbig(segtree[now],tar);
	int mid = (l+r)>>1;
	if(mid>=e)return getans(now*2+1,l,mid,s,e,tar);
	else if(mid<s)return getans(now*2+2,mid+1,r,s,e,tar);
	else return max(getans(now*2+1,l,mid,s,e,tar),getans(now*2+2,mid+1,r,s,e,tar));
}

void dfs(int now){
	dp[now] ^= arr[now];
	eul[now].fs = ++C;
	for(auto nxt:tree[now]){
		dp[nxt]^= dp[now];dfs(nxt);
	}
	eul[now].sc = C;
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int q;
	cin>>q;
	C = 1;
	for(int i = 0;i<q;i++){
		string s;
		cin>>s>>get<1>(req[i])>>get<2>(req[i]);
		if(s[0] == 'A')get<0>(req[i]) = 0;
		else get<0>(req[i]) = 1;
		if(get<0>(req[i]) == 0){
			tree[get<1>(req[i])].push_back(++C);
			get<1>(req[i]) = C;
			arr[C] = get<2>(req[i]);
		}
	}
	C = 0;
	dfs(1);
	modify(0,0,C,eul[1].fs,0);
	for(int i = 0;i<q;i++){
		if(!get<0>(req[i])){
			int p = get<1>(req[i]);
			modify(0,0,C,eul[p].fs,dp[p]);
		}
		else{
			int a = get<1>(req[i]),b = get<2>(req[i]);
			cout<<getans(0,0,C,eul[b].fs,eul[b].sc,dp[a])<<'\n';
		}
	}
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Output is correct
2 Correct 2 ms 11356 KB Output is correct
3 Correct 2 ms 11352 KB Output is correct
4 Correct 2 ms 11612 KB Output is correct
5 Correct 2 ms 11356 KB Output is correct
6 Correct 2 ms 11356 KB Output is correct
7 Correct 2 ms 11352 KB Output is correct
8 Correct 2 ms 11612 KB Output is correct
9 Correct 2 ms 11356 KB Output is correct
10 Correct 2 ms 11352 KB Output is correct
11 Correct 2 ms 11356 KB Output is correct
12 Correct 3 ms 11608 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Output is correct
2 Correct 2 ms 11356 KB Output is correct
3 Correct 2 ms 11352 KB Output is correct
4 Correct 2 ms 11612 KB Output is correct
5 Correct 2 ms 11356 KB Output is correct
6 Correct 2 ms 11356 KB Output is correct
7 Correct 2 ms 11352 KB Output is correct
8 Correct 2 ms 11612 KB Output is correct
9 Correct 2 ms 11356 KB Output is correct
10 Correct 2 ms 11352 KB Output is correct
11 Correct 2 ms 11356 KB Output is correct
12 Correct 3 ms 11608 KB Output is correct
13 Correct 5 ms 12124 KB Output is correct
14 Correct 6 ms 13236 KB Output is correct
15 Correct 6 ms 14424 KB Output is correct
16 Correct 7 ms 15192 KB Output is correct
17 Correct 4 ms 12120 KB Output is correct
18 Correct 5 ms 13148 KB Output is correct
19 Correct 6 ms 14172 KB Output is correct
20 Correct 6 ms 14940 KB Output is correct
21 Correct 4 ms 12124 KB Output is correct
22 Correct 5 ms 12948 KB Output is correct
23 Correct 6 ms 14172 KB Output is correct
24 Correct 6 ms 14940 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 884 ms 138384 KB Output is correct
2 Correct 1014 ms 272008 KB Output is correct
3 Runtime error 3055 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Output is correct
2 Correct 2 ms 11356 KB Output is correct
3 Correct 2 ms 11352 KB Output is correct
4 Correct 2 ms 11612 KB Output is correct
5 Correct 2 ms 11356 KB Output is correct
6 Correct 2 ms 11356 KB Output is correct
7 Correct 2 ms 11352 KB Output is correct
8 Correct 2 ms 11612 KB Output is correct
9 Correct 2 ms 11356 KB Output is correct
10 Correct 2 ms 11352 KB Output is correct
11 Correct 2 ms 11356 KB Output is correct
12 Correct 3 ms 11608 KB Output is correct
13 Correct 5 ms 12124 KB Output is correct
14 Correct 6 ms 13236 KB Output is correct
15 Correct 6 ms 14424 KB Output is correct
16 Correct 7 ms 15192 KB Output is correct
17 Correct 4 ms 12120 KB Output is correct
18 Correct 5 ms 13148 KB Output is correct
19 Correct 6 ms 14172 KB Output is correct
20 Correct 6 ms 14940 KB Output is correct
21 Correct 4 ms 12124 KB Output is correct
22 Correct 5 ms 12948 KB Output is correct
23 Correct 6 ms 14172 KB Output is correct
24 Correct 6 ms 14940 KB Output is correct
25 Correct 884 ms 138384 KB Output is correct
26 Correct 1014 ms 272008 KB Output is correct
27 Runtime error 3055 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -