Submission #1091216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091216		kawaii	Klasika (COCI20_klasika)	C++17	33 / 110	1556 ms	524288 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define fi first
#define se second

const int MAXN = 2e5 + 5;
int t, n, m, k, node = 1, val[MAXN], tin[MAXN], tout[MAXN], cnt = 0, max_dist = 0;
string s;
vector<int> adj[MAXN];
mt19937_64 rng;

struct Query{
    char ch;
    int x, y;
};

Query q[MAXN];

void dfs(int u){
    tin[u] = ++cnt;
    for(auto i: adj[u]) dfs(i);
    tout[u] = cnt;
}

struct Node{
    int size = 0;
    vector<int> next[2];
    void add(int x){
        if(!size){   
            next[0].push_back(0);
            next[1].push_back(0);
        }
        int crr_id = 0;
        for(int i = 30; i >= 0; i--){
            bool bit = (((1 << i) & x) > 0);
            if(!next[bit][crr_id]){
                next[0].push_back(0);
                next[1].push_back(0);
                next[bit][crr_id] = ++size;
            }
            crr_id = next[bit][crr_id];
        }
    }
    int query(int x){
        if(!size){   
            next[0].push_back(0);
            next[1].push_back(0);
        }
        int crr_id = 0, ans = 0;
        for(int i = 30; i >= 0; i--){
            bool bit = !((1 << i) & x);
            if(!next[bit][crr_id]) bit = !bit;
            else ans |= (1 << i);
            crr_id = next[bit][crr_id]; 
        }
        return ans;
    }
};

Node st[MAXN * 4];

int get(int crr, int l, int r, int lf, int rt, int val){
    if(l > rt || r < lf) return 0;
    if(lf <= l && r <= rt && r - l + 1 <= max_dist) return st[crr].query(val);
    int mid = l + r >> 1;
    return max(get(crr * 2, l, mid, lf, rt, val), get(crr * 2 + 1, mid + 1, r, lf, rt, val));
}

void update(int crr, int l, int r, int id, int val){
    if(l > id || r < id) return;
    if(l == r){
        if(r - l + 1 <= max_dist) st[crr].add(val);
        return;
    }
    int mid = l + r >> 1;
    update(crr * 2, l, mid, id, val);
    update(crr * 2 + 1, mid + 1, r, id, val);
    if(r - l + 1 <= max_dist) st[crr].add(val);
}

void solve(){
    dfs(1);
    node = 1;
    max_dist = max(1, cnt / 32);
    for(int i = 1; i <= n; i++){
        if(q[i].ch == 'A') node++, update(1, 1, cnt, tin[node], val[node]);
        else{
            int ans = get(1, 1, cnt, tin[q[i].y], tout[q[i].y], val[q[i].x]);
            if(tin[q[i].y] == 1) ans = max(ans, val[q[i].x]);
            cout << ans << "\n";
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
    // rng.seed((int)main ^ time(0));
    #ifdef Kawaii
        auto starttime = chrono::high_resolution_clock::now();
    #endif

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> s >> q[i].x >> q[i].y;
        if(s == "Add"){
            q[i].ch = 'A';
            val[++node] = val[q[i].x] ^ q[i].y;
            adj[q[i].x].push_back(node);
        }
        else q[i].ch = 'Q';
    }
    solve();

    #ifdef Kawaii
        auto endtime = chrono::high_resolution_clock::now();
        auto duration = chrono::duration_cast<chrono::milliseconds>(endtime - starttime).count(); 
        cout << "\n=====" << "\nUsed: " << duration << " ms\n";
    #endif
}

Compilation message (stderr)

klasika.cpp: In function 'int get(int, int, int, int, int, int)':
klasika.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |     int mid = l + r >> 1;
      |               ~~^~~
klasika.cpp: In function 'void update(int, int, int, int, int)':
klasika.cpp:76:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |     int mid = l + r >> 1;
      |               ~~^~~

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