oj.uz

Submission #223354

# Submission time Handle Problem Language Result Execution time Memory
223354 2020-04-15T07:44:17 Z errorgorn Klasika (COCI20_klasika) C++14
110 / 110
 3578 ms 221308 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'

struct node{
	int s,e,m;
	set<int> val;
	
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		val.insert(1<<30);
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,int j){
		val.insert(j);
		if (s==e) return;
		else if (i<=m) l->update(i,j);
		else r->update(i,j);
	}
	
	int query(int i,int j,int k){
		if (s==i && e==j){
			int curr=0;
			for (int x=29;~x;x--){
				if (k&(1<<x)){
					//can we find something with 0 bit
					if ((*val.lower_bound(curr))>=curr+(1<<x)) curr^=(1<<x);
				}
				else{
					//1-bit is better
					if ((*val.lower_bound(curr+(1<<x)))<curr+(2<<x)) curr^=(1<<x);
				}
			}
			return curr^k;
		}
		else if (j<=m) return l->query(i,j,k);
		else if (m<i) return r->query(i,j,k);
		else return max(l->query(i,m,k),r->query(m+1,j,k));
	}
}*root=new node(0,200005);

struct Q{
	char t;
	int a,b;
	
	Q (char _t,int _a,int _b){
		t=_t,a=_a,b=_b;
	}
};

int n;
vector<int> al[200005];
int val[200005];
int in[200005];
int out[200005];

int DFS_TIME=0;
void dfs(int i,int p){
	in[i]=++DFS_TIME;
	for (auto &it:al[i]){
		if (it==p) continue;
		
		dfs(it,i);
	}
	out[i]=DFS_TIME;
}

vector<Q> queries;

inline void read(int& x) {
    x = 0;
    char ch = getchar_unlocked();
    while (ch&16){ //this will break when ‘\n’ or ‘ ‘ is encountered
		x = (x << 3) + (x << 1) + (ch&15);
		ch = getchar_unlocked();
	}
}

inline void read(char& x) {
	x=getchar_unlocked();
    char ch = getchar_unlocked();
    while (ch&64) ch=getchar_unlocked();
}



int main(){	
	ios::sync_with_stdio(0);
	cout.tie(0);
	
	read(n);
	
	char s;
	int a,b;
	for (int x=0;x<n;x++){
		read(s),read(a),read(b);
		queries.push_back(Q(s,a,b));
	}
	
	int index=2;
	for (auto &it:queries){
		if (it.t=='A'){
			al[it.a].push_back(index);
			al[index].push_back(it.a);
			
			val[index]=val[it.a]^it.b;
			index++;
		}
	}
	
	dfs(1,-1);
	
	//for (int x=1;x<index;x++) cout<<val[x]<<" "<<in[x]<<" "<<out[x]<<endl;
	root->update(in[1],val[1]); //oof

	index=2;
	for (auto &it:queries){
		if (it.t=='A'){
			//cout<<in[index]<<" "<<val[index]<<endl;
			root->update(in[index],val[index]);
			index++;
		}
		else{
			//cout<<in[it.b]<<" "<<out[it.b]<<" "<<val[it.a]<<endl;
			if (it.b!=1) cout<<root->query(in[it.b],out[it.b],val[it.a])<<endl;
			else cout<<root->query(0,200005,val[it.a])<<endl;
		}
	}
}

Compilation message

klasika.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("Ofast")
 
klasika.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
klasika.cpp:4:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
klasika.cpp: In constructor 'node::node(int, int)':
klasika.cpp:21:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   s=_s,e=_e,m=s+e>>1;
               ~^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 61432 KB Output is correct
2 Correct 55 ms 61432 KB Output is correct
3 Correct 56 ms 61560 KB Output is correct
4 Correct 55 ms 61560 KB Output is correct
5 Correct 55 ms 61432 KB Output is correct
6 Correct 56 ms 61432 KB Output is correct
7 Correct 56 ms 61560 KB Output is correct
8 Correct 55 ms 61560 KB Output is correct
9 Correct 54 ms 61432 KB Output is correct
10 Correct 57 ms 61432 KB Output is correct
11 Correct 56 ms 61560 KB Output is correct
12 Correct 57 ms 61560 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 61432 KB Output is correct
2 Correct 55 ms 61432 KB Output is correct
3 Correct 56 ms 61560 KB Output is correct
4 Correct 55 ms 61560 KB Output is correct
5 Correct 55 ms 61432 KB Output is correct
6 Correct 56 ms 61432 KB Output is correct
7 Correct 56 ms 61560 KB Output is correct
8 Correct 55 ms 61560 KB Output is correct
9 Correct 54 ms 61432 KB Output is correct
10 Correct 57 ms 61432 KB Output is correct
11 Correct 56 ms 61560 KB Output is correct
12 Correct 57 ms 61560 KB Output is correct
13 Correct 64 ms 61816 KB Output is correct
14 Correct 66 ms 62332 KB Output is correct
15 Correct 69 ms 62712 KB Output is correct
16 Correct 65 ms 63096 KB Output is correct
17 Correct 59 ms 61816 KB Output is correct
18 Correct 59 ms 62200 KB Output is correct
19 Correct 60 ms 62584 KB Output is correct
20 Correct 62 ms 62968 KB Output is correct
21 Correct 61 ms 61816 KB Output is correct
22 Correct 63 ms 62200 KB Output is correct
23 Correct 61 ms 62584 KB Output is correct
24 Correct 61 ms 62968 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 814 ms 104544 KB Output is correct
2 Correct 1020 ms 143076 KB Output is correct
3 Correct 1184 ms 180804 KB Output is correct
4 Correct 1260 ms 219232 KB Output is correct
5 Correct 977 ms 102648 KB Output is correct
6 Correct 1453 ms 141792 KB Output is correct
7 Correct 1903 ms 177760 KB Output is correct
8 Correct 2353 ms 214372 KB Output is correct
9 Correct 826 ms 104800 KB Output is correct
10 Correct 1075 ms 142176 KB Output is correct
11 Correct 1268 ms 179044 KB Output is correct
12 Correct 1363 ms 215396 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 61432 KB Output is correct
2 Correct 55 ms 61432 KB Output is correct
3 Correct 56 ms 61560 KB Output is correct
4 Correct 55 ms 61560 KB Output is correct
5 Correct 55 ms 61432 KB Output is correct
6 Correct 56 ms 61432 KB Output is correct
7 Correct 56 ms 61560 KB Output is correct
8 Correct 55 ms 61560 KB Output is correct
9 Correct 54 ms 61432 KB Output is correct
10 Correct 57 ms 61432 KB Output is correct
11 Correct 56 ms 61560 KB Output is correct
12 Correct 57 ms 61560 KB Output is correct
13 Correct 64 ms 61816 KB Output is correct
14 Correct 66 ms 62332 KB Output is correct
15 Correct 69 ms 62712 KB Output is correct
16 Correct 65 ms 63096 KB Output is correct
17 Correct 59 ms 61816 KB Output is correct
18 Correct 59 ms 62200 KB Output is correct
19 Correct 60 ms 62584 KB Output is correct
20 Correct 62 ms 62968 KB Output is correct
21 Correct 61 ms 61816 KB Output is correct
22 Correct 63 ms 62200 KB Output is correct
23 Correct 61 ms 62584 KB Output is correct
24 Correct 61 ms 62968 KB Output is correct
25 Correct 814 ms 104544 KB Output is correct
26 Correct 1020 ms 143076 KB Output is correct
27 Correct 1184 ms 180804 KB Output is correct
28 Correct 1260 ms 219232 KB Output is correct
29 Correct 977 ms 102648 KB Output is correct
30 Correct 1453 ms 141792 KB Output is correct
31 Correct 1903 ms 177760 KB Output is correct
32 Correct 2353 ms 214372 KB Output is correct
33 Correct 826 ms 104800 KB Output is correct
34 Correct 1075 ms 142176 KB Output is correct
35 Correct 1268 ms 179044 KB Output is correct
36 Correct 1363 ms 215396 KB Output is correct
37 Correct 3505 ms 106772 KB Output is correct
38 Correct 3578 ms 144896 KB Output is correct
39 Correct 3197 ms 183904 KB Output is correct
40 Correct 2378 ms 221308 KB Output is correct
41 Correct 855 ms 104544 KB Output is correct
42 Correct 1262 ms 141172 KB Output is correct
43 Correct 1751 ms 177412 KB Output is correct
44 Correct 2228 ms 213720 KB Output is correct
45 Correct 1505 ms 104420 KB Output is correct
46 Correct 1737 ms 141696 KB Output is correct
47 Correct 1772 ms 178052 KB Output is correct
48 Correct 1713 ms 215136 KB Output is correct