oj.uz

Submission #868773

# Submission time Handle Problem Language Result Execution time Memory
868773 2023-11-02T01:58:16 Z pcc Klasika (COCI20_klasika) C++14
33 / 110
 3228 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;
vector<int> tree[mxn];
int arr[mxn],dp[mxn];
pii eul[mxn];
pii trie[mxn*200];
int segtree[mxn*4];
int ppp = 0;
int C = 0;
tiii req[mxn];

int newnode(){
	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 8536 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 5 ms 9564 KB Output is correct
14 Correct 5 ms 10472 KB Output is correct
15 Correct 6 ms 11612 KB Output is correct
16 Correct 6 ms 12636 KB Output is correct
17 Correct 3 ms 9308 KB Output is correct
18 Correct 4 ms 10332 KB Output is correct
19 Correct 5 ms 11356 KB Output is correct
20 Correct 6 ms 12380 KB Output is correct
21 Correct 4 ms 9476 KB Output is correct
22 Correct 4 ms 10332 KB Output is correct
23 Correct 5 ms 11352 KB Output is correct
24 Correct 6 ms 12380 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 845 ms 136272 KB Output is correct
2 Correct 952 ms 269980 KB Output is correct
3 Runtime error 3228 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 8536 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 5 ms 9564 KB Output is correct
14 Correct 5 ms 10472 KB Output is correct
15 Correct 6 ms 11612 KB Output is correct
16 Correct 6 ms 12636 KB Output is correct
17 Correct 3 ms 9308 KB Output is correct
18 Correct 4 ms 10332 KB Output is correct
19 Correct 5 ms 11356 KB Output is correct
20 Correct 6 ms 12380 KB Output is correct
21 Correct 4 ms 9476 KB Output is correct
22 Correct 4 ms 10332 KB Output is correct
23 Correct 5 ms 11352 KB Output is correct
24 Correct 6 ms 12380 KB Output is correct
25 Correct 845 ms 136272 KB Output is correct
26 Correct 952 ms 269980 KB Output is correct
27 Runtime error 3228 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -