oj.uz

Submission #868888

# Submission time Handle Problem Language Result Execution time Memory
868888 2023-11-02T11:54:22 Z pcc Klasika (COCI20_klasika) C++14
110 / 110
 1267 ms 174084 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 magic = 2000;
const int SZ = mxn*150;
int head[mxn],nedge[mxn],dir[mxn];
bitset<mxn> active;
int arr[mxn],dp[mxn];
pii eul[mxn];
pii trie[SZ];
int brr[mxn];
int segtree[mxn*4];
int ppp = 0;
int ptr = 0;
int C = 0;
tiii req[mxn];
 
void addedge(int s,int e){
	ptr++;
	nedge[ptr] = head[s];
	head[s] = ptr;
	dir[ptr] = e;
	return;
}
 
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(r-l<magic)return;
	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(r-l<magic*2){
		int re = -1;
		//cout<<l<<' '<<r<<' '<<s<<' '<<e<<' '<<tar<<endl;
		for(int i = max(l,s);i<=min(e,r);i++){
			if(!active[i])continue;
			re = max(re,brr[i]^tar);
		}
		return re;
	}
 
	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;
	while(head[now] != 0){
		int tmp = head[now];
		int nxt = dir[tmp];
		dp[nxt] ^= dp[now];
		dfs(nxt);
		head[now] = nedge[tmp];
	}
	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){
			addedge(get<1>(req[i]),++C);
			get<1>(req[i]) = C;
			arr[C] = get<2>(req[i]);
		}
	}
	C = 0;
	dfs(1);
	for(int i = 1;i<=C;i++){
		brr[eul[i].fs] = dp[i];
	}
	active[eul[1].fs] = true;
	modify(0,0,C,eul[1].fs,0);
	/*
	for(int i = 1;i<=C;i++){
		cout<<eul[i].fs<<','<<eul[i].sc<<' ';
	}cout<<endl;
 
   */
	for(int i = 0;i<q;i++){
		if(!get<0>(req[i])){
			int p = get<1>(req[i]);
			active[eul[p].fs] = true;
			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 1 ms 8536 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 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 1 ms 8540 KB Output is correct
9 Correct 1 ms 8640 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8792 KB Output is correct
12 Correct 2 ms 8548 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 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 1 ms 8540 KB Output is correct
9 Correct 1 ms 8640 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8792 KB Output is correct
12 Correct 2 ms 8548 KB Output is correct
13 Correct 3 ms 8540 KB Output is correct
14 Correct 3 ms 8792 KB Output is correct
15 Correct 3 ms 8792 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 2 ms 8536 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 2 ms 8540 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct
22 Correct 2 ms 8540 KB Output is correct
23 Correct 2 ms 8540 KB Output is correct
24 Correct 2 ms 8540 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1067 ms 45828 KB Output is correct
2 Correct 1010 ms 86100 KB Output is correct
3 Correct 1103 ms 117760 KB Output is correct
4 Correct 748 ms 173892 KB Output is correct
5 Correct 1246 ms 43588 KB Output is correct
6 Correct 1114 ms 81140 KB Output is correct
7 Correct 1267 ms 110492 KB Output is correct
8 Correct 808 ms 164008 KB Output is correct
9 Correct 967 ms 43860 KB Output is correct
10 Correct 929 ms 82304 KB Output is correct
11 Correct 954 ms 112304 KB Output is correct
12 Correct 660 ms 165712 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 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 1 ms 8540 KB Output is correct
9 Correct 1 ms 8640 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8792 KB Output is correct
12 Correct 2 ms 8548 KB Output is correct
13 Correct 3 ms 8540 KB Output is correct
14 Correct 3 ms 8792 KB Output is correct
15 Correct 3 ms 8792 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 2 ms 8536 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 2 ms 8540 KB Output is correct
21 Correct 2 ms 8540 KB Output is correct
22 Correct 2 ms 8540 KB Output is correct
23 Correct 2 ms 8540 KB Output is correct
24 Correct 2 ms 8540 KB Output is correct
25 Correct 1067 ms 45828 KB Output is correct
26 Correct 1010 ms 86100 KB Output is correct
27 Correct 1103 ms 117760 KB Output is correct
28 Correct 748 ms 173892 KB Output is correct
29 Correct 1246 ms 43588 KB Output is correct
30 Correct 1114 ms 81140 KB Output is correct
31 Correct 1267 ms 110492 KB Output is correct
32 Correct 808 ms 164008 KB Output is correct
33 Correct 967 ms 43860 KB Output is correct
34 Correct 929 ms 82304 KB Output is correct
35 Correct 954 ms 112304 KB Output is correct
36 Correct 660 ms 165712 KB Output is correct
37 Correct 603 ms 46504 KB Output is correct
38 Correct 597 ms 86428 KB Output is correct
39 Correct 655 ms 118692 KB Output is correct
40 Correct 529 ms 174084 KB Output is correct
41 Correct 118 ms 43920 KB Output is correct
42 Correct 224 ms 81548 KB Output is correct
43 Correct 324 ms 110664 KB Output is correct
44 Correct 461 ms 163712 KB Output is correct
45 Correct 288 ms 44020 KB Output is correct
46 Correct 315 ms 82240 KB Output is correct
47 Correct 386 ms 111972 KB Output is correct
48 Correct 469 ms 166096 KB Output is correct