Submission #596946

#	Time	Username	Problem	Language	Result	Execution time	Memory
596946		tht2005	Klasika (COCI20_klasika)	C++17	110 / 110	407 ms	187784 KiB

klasika

#include <bits/stdc++.h>

using namespace std;

#define L 30
#define Q 200005

struct node_t {
    int sz, val;
    node_t* c[2];
    node_t(int vv = Q) : sz(0), val(vv) {
        c[0] = c[1] = NULL;
    }
};
void insert(node_t* p, int x, int val) {
    for(int i = L; i--; ) {
        int e = x >> i & 1;
        if(p->c[e] == NULL) {
            p->c[e] = new node_t(val);
        }
        p = p->c[e];
        ++p->sz;
    }
}
int query(node_t* p, int x, int val) {
    int ret = 0;
    for(int i = L; i--; ) {
        int e = (x >> i & 1) ^ 1;
        if(p->c[e] && p->c[e]->val < val) {
            ret |= 1 << i;
        }
        else {
            e ^= 1;
        }
        p = p->c[e];
    }
    return ret;
}
node_t* merge(node_t* a, node_t* b) {
    if(!a || !b) {
        return a ? a : b;
    }
    if(b->sz < a->sz) {
        swap(a, b);
    }
    a->sz += (b->c[0] ? b->c[0]->sz : 0) + (b->c[1] ? b->c[1]->sz : 0);
    a->val = min(a->val, b->val);
    a->c[0] = merge(a->c[0], b->c[0]);
    a->c[1] = merge(a->c[1], b->c[1]);
    return a;
}

int n = 1, s[Q], res[Q];
node_t* rt[Q];
vector<int> aj[Q];
vector<pair<int, int>> queries[Q];

void dfs(int v) {
    for(int u : aj[v]) {
        dfs(u);
        rt[v] = merge(rt[v], rt[u]);
    }
    for(const auto& [u, i] : queries[v]) {
        res[i] = query(rt[v], s[u], i);
    }
}

int main() {
    int q;
    scanf("%d", &q);
    rt[1] = new node_t();
    insert(rt[1], 0, 0);
    for(int i = 1; i <= q; ++i) {
        char o;
        int x, y;
        scanf(" %c%*s %d %d", &o, &x, &y);
        if(o == 'A') {
            ++n;
            aj[x].push_back(n);
            s[n] = s[x] ^ y;
            rt[n] = new node_t();
            insert(rt[n], s[n], i);
            res[i] = -1;
        }
        else {
            queries[y].emplace_back(x, i);
        }
    }
    dfs(1);
    for(int i = 1; i <= q; ++i) {
        if(res[i] != -1) {
            printf("%d\n", res[i]);
        }
    }
    return 0;
}

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
klasika.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf(" %c%*s %d %d", &o, &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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