oj.uz

Submission #868777

# Submission time Handle Problem Language Result Execution time Memory
868777 2023-11-02T02:04:50 Z pcc Klasika (COCI20_klasika) C++14
33 / 110
 3103 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*175;
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 8536 KB Output is correct
2 Correct 2 ms 8428 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 3 ms 8760 KB Output is correct
9 Correct 3 ms 8536 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 2 ms 8540 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 8428 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 3 ms 8760 KB Output is correct
9 Correct 3 ms 8536 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 6 ms 9308 KB Output is correct
14 Correct 6 ms 10332 KB Output is correct
15 Correct 6 ms 11356 KB Output is correct
16 Correct 7 ms 12380 KB Output is correct
17 Correct 4 ms 9304 KB Output is correct
18 Correct 5 ms 10332 KB Output is correct
19 Correct 6 ms 11356 KB Output is correct
20 Correct 7 ms 12376 KB Output is correct
21 Correct 5 ms 9308 KB Output is correct
22 Correct 5 ms 10328 KB Output is correct
23 Correct 6 ms 11356 KB Output is correct
24 Correct 7 ms 12152 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 865 ms 136164 KB Output is correct
2 Correct 985 ms 270012 KB Output is correct
3 Runtime error 3103 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 8428 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 3 ms 8760 KB Output is correct
9 Correct 3 ms 8536 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 2 ms 8540 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 6 ms 9308 KB Output is correct
14 Correct 6 ms 10332 KB Output is correct
15 Correct 6 ms 11356 KB Output is correct
16 Correct 7 ms 12380 KB Output is correct
17 Correct 4 ms 9304 KB Output is correct
18 Correct 5 ms 10332 KB Output is correct
19 Correct 6 ms 11356 KB Output is correct
20 Correct 7 ms 12376 KB Output is correct
21 Correct 5 ms 9308 KB Output is correct
22 Correct 5 ms 10328 KB Output is correct
23 Correct 6 ms 11356 KB Output is correct
24 Correct 7 ms 12152 KB Output is correct
25 Correct 865 ms 136164 KB Output is correct
26 Correct 985 ms 270012 KB Output is correct
27 Runtime error 3103 ms 524288 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -