Submission #223284

#	Time	Username	Problem	Language	Result	Execution time	Memory
223284		lyc	Klasika (COCI20_klasika)	C++14	33 / 110	2955 ms	524292 KiB

klasika

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

#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int MX_Q = 2e5+5;
const int MX_N = 2e5+5;

int Q;
struct Query { int t, x, y; } query[MX_Q]; // 0 for add, 1 for query

int N;
vector<pair<int,int>> al[MX_N];
int dt, pre[MX_N], pst[MX_N], dist[MX_N];

void dfs(int u) {
    pre[u] = ++dt;
    for (auto v : al[u]) {
        dist[v.first] = dist[u] ^ v.second;
        dfs(v.first);
    }
    pst[u] = dt;
}

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

template <typename T>
using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct node {
    pbds_set<int> v;
    int depth, bit;
    node *l, *r;

    node(int depth, int bit): depth(depth), bit(bit), l(NULL), r(NULL) {}

    bool createChildren() {
        if (l != NULL) return 0;
        l = new node(depth-1, 0);
        r = new node(depth-1, 1);
        return 1;
    }

    void update(int bm, int x) {
        //if (depth < 5) cout << "Updating node " << depth << " " << bit << " :: " << bm << " " << x << endl;
        v.insert(x);
        if (depth == 0) return;
        createChildren();
        if ((bm&(1<<(depth-1))) == 0) l->update(bm,x);
        else r->update(bm,x);
    }

    bool contains(int x, int y) {
        return v.order_of_key(y+1) - v.order_of_key(x) > 0;
    }

    int query(int x, int y, int bm) {
        //if (depth < 5) cout << "Querying node " << depth << " " << bit << " :: " << x << " " << y << " " << bm << " contains? " << contains(x,y) << " sz " << SZ(v) << endl;
        if (depth == 0) return bit;
        int b = bm&(1<<(depth-1));
        if ((b && l->contains(x,y)) || (!r->contains(x,y))) return (bit<<depth) | l->query(x,y,bm);
        return (bit<<depth) | r->query(x,y,bm);
    }
} btree(31,0);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    N = 1;
    cin >> Q;
    FOR(i,1,Q){
        string S; int X, Y; cin >> S >> X >> Y;
        if (S == "Add") {
            al[X].emplace_back(++N,Y);
            query[i] = { 0,N,-1 };
        } else {
            query[i] = { 1,X,Y };
        }
    }

    dt = 0, dist[1] = 0, dfs(1);
    //FOR(i,1,N){
    //    cout << i << " :: " << pre[i] << " " << pst[i] << " :: " << dist[i] << endl;
    //}

    btree.update(0, 1);
    FOR(i,1,Q){
        Query q = query[i];
        //cout << "query " << i << endl;
        if (q.t == 0) {
            btree.update(dist[q.x], pre[q.x]);
        } else {
            cout << (dist[q.x] ^ btree.query(pre[q.y], pst[q.y], dist[q.x])) << '\n';
        }
    }
}

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