Submission #1291322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291322		nghiaxtoneri	Klasika (COCI20_klasika)	C++20	110 / 110	460 ms	199748 KiB

klasika

#include <bits/stdc++.h>
#define endl '\n'
#define mask(n) (1<<(n))

using namespace std;

const int PZ = 29;
const int maxn = 2e5 + 5;
const int inf = 1e9;

struct node{
    int min_time, sz;
    
    node* child[2];
    node(){
        min_time = inf;
        sz = 1;
        for (int i = 0; i < 2; i++) child[i] = NULL;
    }
};

vector <pair <int, int>> query[maxn], ans;

struct trie{
    node* root;
    trie(){
        root = new node();
    }
    
    void add(int n, int tim){
        node *u = root;
        for (int i = PZ; i >= 0; i--){
            bool c = n & mask(i);
            if (!u->child[c]) u->child[c] = new node();
            u = u->child[c];
            u->min_time = min(u->min_time, tim);
        }
    }
    
    int solve(int n, int timer){
        int ans = 0;
        node *u = root;
        for (int i = PZ; i >= 0; i--){
            bool c = n & mask(i);
            if (u->child[!c] && u->child[!c]->min_time < timer){
                u = u->child[!c];
                ans += mask(i);
            } else u = u->child[c];
        }
        return ans;
    }
    
    
} Trie[maxn];

struct trngthaonghi{
    string type;
    int x, y;
} queries[maxn];

vector <int> g[maxn];
int timer[maxn], cost[maxn], xr[maxn];

node* merge_node(node* a, node* b){
    if(!a) return b;
    if(!b) return a;

    if(a->sz < b->sz) swap(a,b);

    a->min_time = min(a->min_time, b->min_time);

    a->child[0] = merge_node(a->child[0], b->child[0]);
    a->child[1] = merge_node(a->child[1], b->child[1]);

    a->sz = 1;
    if(a->child[0]) a->sz += a->child[0]->sz;
    if(a->child[1]) a->sz += a->child[1]->sz;

    return a;
}

void merge_trie(trie &A, trie &B){
    A.root = merge_node(A.root, B.root);
}

void pre_dfs(int u, int p){
    xr[u] = cost[u] ^ xr[p];

    for (int v : g[u]){
        if (v == p) continue;
        pre_dfs(v, u);
    }
}

void dfs(int u, int p){
    Trie[u].add(xr[u], timer[u]);
    
    for (int v: g[u]){
        if (v == p) continue;
        dfs(v, u);
        merge_trie(Trie[u], Trie[v]);
    }
    
    for (pair <int, int> cur: query[u]){
        int node = cur.first;
        int idx = cur.second;
        int res = Trie[u].solve(xr[node], idx);
        ans.push_back({idx, res});
    }
}

#define phtrnghia "TEST"

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    // if (fopen(phtrnghia".INP", "r")){
    //     freopen(phtrnghia".INP", "r", stdin);
    //     freopen(phtrnghia".OUT", "w", stdout);
    // }
    
    int q, n = 1;
    cin >> q;

    for (int i = 1; i <= q; i++){
        string type;
        int x, y;
        cin >> type >> x >> y;

        if (type == "Add"){
            n++;
            g[x].push_back(n);
            timer[n] = i;
            cost[n] = y;
        } 
        
        if (type == "Query") query[y].push_back({x, i});
    }

    pre_dfs(1, 0);
    dfs(1, 0);
    sort(ans.begin(), ans.end());
    for (pair <int, int> cur: ans) cout << cur.second << endl;
    
    return 0;
}

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