Submission #1125739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125739		ducanh0811	Klasika (COCI20_klasika)	C++20	110 / 110	1979 ms	427628 KiB

klasika

/**

    time: 5:58PM Tue 12/10/2024
    author: Nium

**/
#include <bits/stdc++.h>
#define         int             long long
#define         fi              first
#define         se              second
#define         pii             pair<int,int>
#define         pb              push_back
#define         eb              emplace_back
#define         MASK(i)         (1ll << (i))
#define         FOR(i,a,b)      for (int i = (a); i <= (b); ++i)
#define         REV(i,a,b)      for (int i = (a); i >= (b); --i)
using namespace std;

#define MAXN 200002
struct query{
    string s;
    int x, y;
    int i;
};

vector<query> Q;

int q, n = 1;

vector<int> g[MAXN];

int pref[MAXN];

struct Node{
    Node* child[2];
    set<int> s;
    Node(){
        child[0] = nullptr;
        child[1] = nullptr;
        s = {};
    }
};

Node* root = new Node();

void add(int x, int t){
    Node* run = root;
    for (int i = 29; i >= 0; --i){
        bool flag = ((x >> i) & 1);
        if (run -> child[flag] == NULL) run -> child[flag] = new Node();
        run = run -> child[flag];
        run -> s.insert(t);
    }
}

int st[MAXN];
int en[MAXN];
int TT = 0;

void dfs(int u){
    st[u] = ++TT;
    for (int &v : g[u]){

        dfs(v);
    }
    en[u] = TT;
}

int Query(int x, int l, int r){
    int trie_num = 0;
    Node* run = root;
    for (int i = 29; i >= 0; --i){
        if (!run) break;
        bool x_bit = ((x >> i) & 1);
        bool ok = true;
        if (run->child[!x_bit] == nullptr) ok = false;
        else {
            Node* vir = run->child[!x_bit];
            auto it = vir->s.lower_bound(l);
            if (it == vir->s.end() || (*it) > r) ok = false;
        }
        if (ok){
            trie_num |= (1 << i);
            run = run->child[!x_bit];
        } else if (run->child[x_bit]){
            run = run->child[x_bit];
        } else break;
    }
    return trie_num;
}

void solve(){
    cin >> q;
    FOR(i,1,q){
        string s; cin >> s;
        int x, y; cin >> x >> y;
        Q.push_back({s, x, y});
        if (s == "Add"){
            n++;
            g[x].push_back(n);
            pref[n] = pref[x] ^ y;
            Q.back().i = n;
        }
    }
    dfs(1);
    add(0, 1);
    for (query &x : Q){
        if (x.s == "Add"){
            add(pref[x.i], st[x.i]);
        } else {
            cout << Query(pref[x.x], st[x.y], en[x.y]) << '\n';
        }
    }
}

#define task ""
int32_t main(){
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    solve();
    return 0;
}

Compilation message (stderr)

klasika.cpp: In function 'int32_t main()':
klasika.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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