oj.uz

Submission #223347

# Submission time Handle Problem Language Result Execution time Memory
223347 2020-04-15T07:35:48 Z errorgorn Klasika (COCI20_klasika) C++14
0 / 110
 57 ms 61432 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;


int main(){	
	ios::sync_with_stdio(0);
    cin.tie(0);
	cout.tie(0);
	
	string s;
	int a,b;
	for (int x=0;x<n;x++){
		cin>>s>>a>>b;
		queries.push_back(Q(s[0],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;
			cout<<root->query(in[it.b],out[it.b],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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 61432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 61432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 61432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 61432 KB Output isn't correct
2 Halted 0 ms 0 KB -