Submission #844890

#	Time	Username	Problem	Language	Result	Execution time	Memory
844890		vjudge1	Klasika (COCI20_klasika)	C++14	110 / 110	2828 ms	442796 KiB

klasika

// Aber der schlimmste Fiend, dem du begegnen kannst, wirst du immer dir selber sein
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ff first
#define ss second
#define pb push_back
#define rev reverse
#define all(x) x.begin(),x.end()
#define acc accumulate
#define sz size()
#define MOD 1000000007
#define rall(x) x.rbegin(),x.rend()
#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const int N = 2e5 + 5;
struct node{
    node *one = NULL, *zero = NULL;
    set<int> index_set;
};
struct trie{
    node root;
    void insert(node *cur, int len, int x, int in){
        cur->index_set.insert(in);
        if(len == -1){
            return;
        }
        int bit = (x >> len) & 1;
        if(bit){
            if(cur->one == NULL){
                cur->one = new node;
            }
            insert(cur->one, len-1, x, in);
        }
        else{
            if(cur->zero == NULL){
                cur->zero = new node;
            }
            insert(cur->zero, len-1, x, in);
        }
    }
    int find(node *cur, int len, int x, int l, int r){
        if(len == -1){
            return 0;
        }
        int bit = (x >> len) & 1;
        if(bit){
            if(cur->zero != NULL && cur->zero->index_set.lower_bound(l) != cur->zero->index_set.upper_bound(r)){
                return find(cur->zero, len-1, x, l, r) + (1 << len);
            }
            else{
                return find(cur->one, len-1, x, l, r);
            }
        }
        if(cur->one != NULL && cur->one->index_set.lower_bound(l) != cur->one->index_set.upper_bound(r)){
           return find(cur->one, len-1, x, l, r) + (1 << len);
        }
        return find(cur->zero, len-1, x, l, r);
    }
};
vector<int> adj[N];
int gir[N], cik[N], ti = 0, xor_value[N];
void dfs(int node, int dad){
    gir[node] = ++ti;
    for(int i = 0; i < adj[node].sz; i++){
        if(adj[node][i] != dad){
            dfs(adj[node][i], node);
        }
    }
    cik[node] = ti;
}
trie tree;
inline void solve(){
    int n;
    cin >> n;
    pair<string, pair<int, int> > a[n];
    int node_count = 1;
    for(int i = 0; i < n; i++){
        cin >> a[i].ff >> a[i].ss.ff >> a[i].ss.ss;
        if(a[i].ff == "Add"){
            node_count++;
            adj[a[i].ss.ff].emplace_back(node_count);
            adj[node_count].emplace_back(a[i].ss.ff);
            xor_value[node_count] = xor_value[a[i].ss.ff] ^ a[i].ss.ss;
        }
    }
    dfs(1, 1);
    node_count = 1;
    tree.insert(&tree.root, 30, 0, 1);
    for(int i = 0; i < n; i++){
        if(a[i].ff == "Add"){
            node_count++;
            tree.insert(&tree.root, 30, xor_value[node_count], gir[node_count]);
        }
        else{
            cout << tree.find(&tree.root, 30, xor_value[a[i].ss.ff], gir[a[i].ss.ss], cik[a[i].ss.ss]) << endl;
        }
    }
}
int main(){
    fast_io
    int t;
    t = 1;
    while(t--) solve();
}

Compilation message (stderr)

klasika.cpp: In function 'void dfs(int, int)':
klasika.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0; i < adj[node].sz; i++){
      |                      ^

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