Submission #344490

#	Time	Username	Problem	Language	Result	Execution time	Memory
344490		limabeans	Klasika (COCI20_klasika)	C++17	110 / 110	2695 ms	445316 KiB

klasika

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


const int LOG = 30;

int q;
char typ[maxn];
int x[maxn], y[maxn];


int tin[maxn];
int tout[maxn];
int dp[maxn];
vector<pair<int,int>> g[maxn];
int cloc = 0;

void dfs(int at, int p) {
    tin[at] = cloc++;
    for (auto ed: g[at]) {
	int to = ed.second;
	if (to == p) continue;
	dp[to] = dp[at] ^ ed.first;
	dfs(to, at);
    }
    tout[at] = cloc++;
}

struct node {
    set<int> st;
    node *ch[2];
    node() {
	ch[0] = ch[1] = NULL;
    }

    bool inrange(int in, int out) {
	auto iter = st.lower_bound(in);
	return iter!=st.end() && *iter<=out;
    }
};


void insert(node *at, int val, int enterTime) {
    for (int i=LOG-1; i>=0; i--) {
	int bit = val>>i&1;
	if (at->ch[bit] == NULL) {
	    at->ch[bit] = new node();
	}
	at = at->ch[bit];
	at->st.insert(enterTime);	
    }

}

node *root;

int qry(int val, int in, int out) {
    assert(in<=out);
    
    node *at = root;
    int res = 0;
    for (int i=LOG-1; i>=0; i--) {
	int bit = val>>i&1;
	if (at->ch[bit^1] == NULL || !at->ch[bit^1]->inrange(in, out)) {
	    at = at->ch[bit];
	    res |= (bit<<i);
	} else {
	    at = at->ch[bit^1];
	    res |= ((bit^1)<<i);
	}
    }

    return res^val;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    
    root = new node();
    cin>>q;

    
    int n = 1;
    
    for (int i=0; i<q; i++) {
	string op;
	cin>>op;
	typ[i]=op[0];
	cin>>x[i];
	cin>>y[i];
	
	if (typ[i]=='A') {
	    ++n;
	    g[x[i]].push_back({y[i], n});
	    x[i] = n;
	}

    }

    dfs(1, 0);
    insert(root, dp[1], tin[1]);
    

    for (int i=0; i<q; i++) {
	if (typ[i]=='A') {
	    int at = x[i];
	    insert(root, dp[at], tin[at]);
	} else {
	    int a = x[i];
	    int b = y[i];
	    int res = qry(dp[a], tin[b], tout[b]);
	    cout<<res<<"\n";
	}
    }
    
    return 0;
}

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