Submission #965541

#	Time	Username	Problem	Language	Result	Execution time	Memory
965541		dosts	Klasika (COCI20_klasika)	C++17	33 / 110	670 ms	524288 KiB

klasika

//Dost SEFEROĞLU
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
const int N = 2e5+100,inf = 1e18,MOD = 1e9+7,B = 30;


struct Trie {
    Trie* children[2] = {NULL,NULL};
    int bas = 0;
    void insert(int x) {
        Trie* cur = this;
        for (int i=30;i>=-1;i--) {
            cur->bas++;
            if (i > -1) {
                bool go = x&(1<<i);
                if (!cur->children[go]) cur->children[go] = new Trie;
                cur = cur->children[go];
            }
        }
    }

    int query(int x) {
        if (!bas) return -inf;
        Trie* cur = this;
        int ans = 0;
        for (int i=30;i>=0;i--) {
            bool go = !(x&(1<<i));
            if (cur->children[go] && cur->children[go]->bas) {
                ans+=(1<<i);
                cur = cur->children[go];
            } else {
                if (!cur->children[!go]) cur->children[!go] = new Trie;
                cur = cur->children[!go];
            }
        }
        return ans;
    }

};


struct ST {
    vector<Trie*> t;

    ST(int nn) {
        t.resize(4*nn+1);
        for (int i=1;i<=4*nn;i++) t[i] = new Trie;
    }

    void update(int node,int l,int r,int p,int put) {
        t[node]->insert(put);
        if (l==r) return;
        int m = (l+r) >> 1;
        if (p <= m) update(2*node,l,m,p,put);
        else update(2*node+1,m+1,r,p,put);
    }
    int query(int node,int l,int r,int L,int R,int v) {
        if (l > R || r < L) return -inf;
        if (l >= L && r <= R) return t[node]->query(v);
        int m = (l+r) >> 1;
        return max(query(2*node,l,m,L,R,v),query(2*node+1,m+1,r,L,R,v)); 
    }
};

vi tin(N),tout(N),d(N),edges[N];
int timer = 1;
void dfs(int node) {
    tin[node] = timer++;
    for (auto it : edges[node]) dfs(it);
    tout[node] = timer-1;
}

void solve() {
    d[1] = 0;
    int curnode = 1;
    int q;
    cin >> q;
    vector<pair<int,pii>> qs(q+1);
    for (int i=1;i<=q;i++) {
        string s;
        cin >> s;
        int node,v;
        cin >> node >> v;
        if (s == "Add") {
            edges[node].push_back(++curnode);
            d[curnode] = d[node]^v; 
        }
        qs[i] = (pair<int,pii>{(s != "Add"), pii{node,v}});
    }
    dfs(1);
    ST st(curnode);
    st.update(1,1,curnode,tin[1],0);
    int curry = 1;
    for (int i=1;i<=q;i++) {
        int type = qs[i].ff;
        if (!type) {
            ++curry;
            st.update(1,1,curnode,tin[curry],d[curry]);
        }
        else {
            auto [a,b] = qs[i].ss;
            cout << st.query(1,1,curnode,tin[b],tout[b],d[a]) << '\n';
        }
    }
}
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Compilation message (stderr)

klasika.cpp:11:29: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   11 | const int N = 2e5+100,inf = 1e18,MOD = 1e9+7,B = 30;
      |                             ^~~~

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