Submission #846015

#	Time	Username	Problem	Language	Result	Execution time	Memory
846015		efedmrlr	Klasika (COCI20_klasika)	C++17	33 / 110	2113 ms	441828 KiB

klasika

#include <bits/stdc++.h>

#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)

using namespace std;

struct TrieNode {
    TrieNode *c[2];
    set<int> st;

    TrieNode() {
        st.clear();
        c[0] = NULL;
        c[1] = NULL;
    }
    bool checkRange(int l, int r) {
        auto lb = st.lower_bound(l), ub = st.upper_bound(r);
        if(ub == st.begin()) return 0;
        if(lb == st.end()) return 0;
        if(ub == st.end() && st.size() < 1) return 0;
        ub--;
        if((*lb) >= l && (*ub) <= r) {
            //cout<<"l:"<<l<<" r:"<<r<<"\n";
            return 1;
        }
        return 0;
    }

    void insert(int num, int disc, int index) {
        st.insert(disc);
        if(index == -1) return;
        bool f = (1 << index) & num;
        if(c[f] == NULL) {
            c[f] = new TrieNode();
        }
        c[f]->insert(num, disc, index-1);

    }
    int query(int num, int l, int r, int index) {
        if(!checkRange(l,r)) {
            return -1;
        } 
        if(index == -1) return 0;
        bool f = (1 << index) & num;
        if(c[f] != NULL) {
            int res = c[f]->query(num,l,r, index-1);
            
            if(res != -1) {
                //cout<<((1 << index) & num) + res<<"\n"; 
                return ((1 << index) & num) + res; 
            }

        }
        if(c[!f] == NULL) {
            return -1;
        };
        int res = ((num ^ INT_MAX) & (1 << index) ) + c[!f]->query(num, l, r, index-1);
        //cout<<res<<"\n";
        return res;
    }


};

const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 2e5+5;
const int MX = 31;

int n,m,q;
vector<array<int,3> > quer;
int timer = 0;
vector<int> tout(N),tin(N);
vector<vector<int> > adj(N);
vector<int> w(N,0), pathw(N,0);

void dfs(int node, int par) {
    tin[node] = timer++;
    pathw[node] = pathw[par] ^ w[node];
    //cout<<"pathw[par]:"<<pathw[par]<<" w[node]:"<<w[node]<<" path[node]:"<< pathw[node]<<"\n";
    for(auto c : adj[node]) {
        if(c == par) continue;
        dfs(c, node);
    }
    tout[node] = timer++;
}

void solve() {
    cin>>q;
    quer.resize(q);
    int cnt = 2;
    for(int i = 0; i<q; i++) {
        string op;
        cin>>op;
        int a,b;
        if(op == "Query") {
            cin>>a>>b;
            quer[i] = {0, a, b};

        }
        else if(op == "Add") {
            cin>>a>>b;
            adj[cnt].pb(a);
            adj[a].pb(cnt);
            //cout<<b<<"?\n";
            w[cnt] = b;
            quer[i] = {1, a, cnt};
            cnt++;
            
        }   
    }
    dfs(1,0);
    TrieNode *root = new TrieNode();
    int ans = 0;
    root->insert(0, tin[1], MX-1);
    
    
    for(int i = 0; i<q; i++) {
        //cout<<"patlamadı:"<<i<<"\n";
        auto cur = quer[i];
        if(cur[0]) {
            root->insert(pathw[cur[2]], tin[cur[2]], MX-1);
        }
        else {
            int x = pathw[cur[1]];
            x = x ^ INT_MAX;
            int tmp = root->query(x, tin[cur[2]], tout[cur[2]], MX-1);
            ans = tmp ^ pathw[cur[1]];
            cout<<ans<<"\n";
        }
    }
    

}
 
signed main() {
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

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