Submission #223325

#	Time	Username	Problem	Language	Result	Execution time	Memory
223325		oolimry	Klasika (COCI20_klasika)	C++14	33 / 110	5049 ms	423072 KiB

klasika

#include <bits/stdc++.h>
#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")

using namespace std;
 
int n = 1;
int cnt = 0;
vector<int> adj[200005];
int low[200005];
int high[200005];
int XOR[200005];
 
void dfs(int u){
	low[u] = cnt;
	high[u] = cnt;
	cnt++;
	for(int v : adj[u]){
		dfs(v);
		high[u] = max(high[u], high[v]);
	}
}
 
typedef pair<int,int> ii;
vector<ii> queries;

struct custom_hash {
    typedef long long ll;
    typedef unsigned long long ull;
    const ull FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    static ull splitmix64(ull x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(ll x) const {
        return splitmix64(x + FIXED_RANDOM);
    }
    size_t operator()(const pair<int,int> &i)const{
        return splitmix64((((ll)i.first)^(((ll)i.second)<<32))+FIXED_RANDOM);
    }
};

unordered_map<int, set<int>, custom_hash > m[33];
 
int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int Q; cin >> Q;
	queries.push_back(ii(-1,0));
	
	for(int i = 0;i <= 30;i++){
		m[i].reserve(4096);
		//changes number of buckets, make it a power of 2 to be fast
		m[i].max_load_factor(0.25);
	}
	
	while(Q--){
		string s; int a, b; 
		cin >> s >> a >> b;
		if(s[0] == 'A' || s[0] == 'a'){
			a--;
			assert(a < n);
			adj[a].push_back(n);
			XOR[n] = XOR[a] ^ b;
			queries.push_back(ii(-1,n));
			n++;
		}
		else{
			assert(a-1 < n);
			assert(b-1 < n);
			queries.push_back(ii(a-1,b-1));
		}
	}
	
	
	dfs(0);
	//for(int i = 0;i < n;i++) cout << low[i] << " " << high[i] << "\n";
	
	for(ii q : queries){
		//cout << q.first << " " << q.second << "\n";
		
		if(q.first == -1){
			int pos = low[q.second];
			int x = XOR[q.second];
			
			for(int b = 0;b <= 30;b++){
				m[b][x].insert(pos);
				x ^= ((x & (1<<b)));
			}
			
			continue;
		}
		
		int other = XOR[q.first];
		int L = low[q.second], R = high[q.second];
		int cur = 0;
		for(int b = 30;b >= 0;b--){
			if((other & (1<<b)) == 0) cur ^= (1 << b);
			
			set<int> &s = m[b][cur];
			auto it = s.lower_bound(L);
			if(it == s.end() || *it > R) cur ^= (1 << b);
		}
		
		cout << (cur ^ other) << "\n";
		
	}
}

Compilation message (stderr)

klasika.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("Ofast")
 
klasika.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
klasika.cpp:5:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44