Submission #1088884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088884		vladilius	Klasika (COCI20_klasika)	C++17	0 / 110	519 ms	524288 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
const int lg = 31;

struct ST{
    struct node{
        node *l, *r;
        node(){
            l = r = 0;
        }
        node(node *ls, node *rs){
            l = ls; r = rs;
        }
    };
    node *rt;
    int n;
    void init(int ns){
        n = ns;
        rt = new node();
    }
    node* add(node *v, int tl, int tr, int& x){
        if (tl == tr) return new node();
        int tm = (tl + tr) / 2;
        if (x <= tm){
            if (!(v -> l)) v -> l = new node();
            return new node(add(v -> l, tl, tm, x), v -> r);
        }
        if (!(v -> r)) v -> r = new node();
        return new node(v -> l, add(v -> r, tm + 1, tr, x));
    }
    void add(int x){
        rt = add(rt, 1, n, x);
    }
    bool get(node *v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return 1;
        int tm = (tl + tr) / 2;
        if (v -> l && get(v -> l, tl, tm, l, r)) return 1;
        if (v -> r && get(v -> r, tm + 1, tr, l, r)) return 1;
        return 0;
    }
    bool get(int l, int r){
        return get(rt, 1, n, l, r);
    }
};

struct TR{
    struct node{
        ST T;
        int nt[2];
        node(int n){
            nt[0] = nt[1] = 0;
            T.init(n);
        }
    };
    vector<node> t;
    int cc, n;
    void init(int ns){
        n = ns;
        t.pb(node(n));
        t.pb(node(n));
        cc = 1;
    }
    vector<int> :: iterator it;
    void add(int x, int p){
        int v = 1;
        for (int i = lg; i >= 0; i--){
            bool bit = (x >> i) & 1;
            if (!t[v].nt[bit]){
                t[v].nt[bit] = ++cc;
                t.pb(node(n));
            }
            v = t[v].nt[bit];
            t[v].T.add(p);
        }
    }
    int get(int l, int r, int x){
        int out = 0, v = 1;
        for (int i = lg; i >= 0; i--){
            bool bit = (x >> i) & 1;
            int k = t[v].nt[!bit];
            if (t[k].T.get(l, r)){
                v = k;
                out += (1 << i);
                continue;
            }
            v = t[v].nt[bit];
        }
        return out;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int q, cc = 1; cin>>q;
    vector<arr3> qs;
    vector<pii> g[q + 1];
    for (int i = 1; i <= q; i++){
        string type; int x, y; cin>>type>>x>>y;
        if (type[0] == 'A'){
            cc++;
            g[x].pb({cc, y});
            qs.pb({0, x, cc});
        }
        else {
            qs.pb({1, x, y});
        }
    }
    int n = cc;
    vector<int> tin(n + 1), tout(n + 1), d(n + 1);
    int timer = 0;
    function<void(int)> fill = [&](int v){
        tin[v] = ++timer;
        for (auto [i, w]: g[v]){
            d[i] = d[v] ^ w;
            fill(i);
        }
        tout[v] = timer;
    };
    fill(1);

    TR T; T.init(n);
    T.add(0, 1);
    for (auto [type, x, y]: qs){
        if (!type){
            T.add(d[y], tin[y]);
        }
        else {
            cout<<T.get(tin[y], tout[y], d[x])<<"\n";
        }
    }
}

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