Submission #328458

#	Time	Username	Problem	Language	Result	Execution time	Memory
328458		BeanZ	Klasika (COCI20_klasika)	C++14	33 / 110	2204 ms	524292 KiB

klasika

// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define endl '\n'
const int N = 2e5 + 5;
const int mod = 123456789;
const long long oo = 1e18;
ll timer = 1, timer2 = 0, timer3 = 1;
ll cost[N], tin[N], tout[N], dp[N * 32][2];
vector<ll> node[N];
set<ll> mem[N * 32];
void dfs(ll u){
    timer2++;
    tin[u] = timer2;
    for (auto j : node[u]){
        dfs(j);
    }
    tout[u] = timer2;
}
void add(ll u, ll p){
    ll now = 1;
    for (int i = 30; i >= 0; i--){
        ll a = ((u & (1 << i)) > 0);
        if (dp[now][a] == 0){
            timer3++;
            dp[now][a] = timer3;
        }
        now = dp[now][a];
        mem[now].insert(p);
    }
}
ll get(ll u, ll l, ll r){
    ll now = 1;
    ll res = 0;
    for (int i = 30; i >= 0; i--){
        ll a = ((u & (1 << i)) > 0);
        ll id = dp[now][1 - a];
        bool flag = true;
        auto it = mem[id].lower_bound(l);
        if (it == mem[id].end() || (*it) > r) flag = false;
        if (flag){
            res = res + (1 << i);
            now = id;
        } else {
            now = dp[now][a];
        }
        /*
        if (u == 0){
            if (it == mem[id].end()) cout << -1 << " ";
            else cout << (*it) << " ";
            cout << id << " ";
        }*/
    }
    //cout << now << " " << res << endl;
    return res;
}
string task[N];
ll x[N], y[N];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("A.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll q;
    cin >> q;
    for (int i = 1; i <= q; i++){
        cin >> task[i];
        if (task[i] == "Add"){
            cin >> x[i] >> y[i];
            timer++;
            cost[timer] = cost[x[i]] ^ y[i];
            node[x[i]].push_back(timer);
            x[i] = timer;
        } else {
            cin >> x[i] >> y[i];
        }
    }
    dfs(1);
    add(0, tin[1]);
    for (int i = 1; i <= q; i++){
        if (task[i] == "Add"){
            add(cost[x[i]], tin[x[i]]);
        } else {
            cout << get(cost[x[i]], tin[y[i]], tout[y[i]]) << endl;
        }
    }
    //cout << dp[1][0] << endl;
}
/*
3
Add 1 9
Add 2 3
Query 1 2
*/

Compilation message (stderr)

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

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