oj.uz

Submission #857084

# Submission time Handle Problem Language Result Execution time Memory
857084 2023-10-05T11:04:57 Z Jethro Klasika (COCI20_klasika) C++17
33 / 110
 502 ms 382460 KB 
//Writed by: Jethro_
//----------------------
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

const int N = 3200005;
int n, node = 1, i, root, val, in[N], out[N], cnt = 0, Xor[N], LG = 31, child[N][2], cnt2 = 0;
vector<pair<int, int>> a[N];
vector<int> save[N];
pair<int, int> query[N];
string type[N];

void add() {
    cin >> n;
    for(i = 1; i <= n; ++i) {
        cin >> type[i];
        if(type[i] == "Add") {
            cin >> root >> val;
            a[++node].push_back({root, val});
            a[root].push_back({node, val});
            
            query[i] = {node, node};
            
        }else {
            cin >> root >> val;
            query[i] = {root, val};
        }
    }
}
void dfs(int u, int p) {
    in[u] = ++cnt;
    for(auto [v, w] : a[u]) {
        if(v == p) continue;
        Xor[v] = Xor[u] ^ w;
        dfs(v, u);
    }

    out[u] = cnt;
}
void ADD(int s, int id) {
    int u = 0;

    for(int i = LG; i >= 0; --i) {
        int k = (s >> i) & 1;
        if(child[u][k] == -1) {
            child[u][k] = ++cnt2;
        }
        u = child[u][k];
        save[u].push_back(in[id]);
    }
}
void get(int s, int l, int r) {
    int u = 0, res = 0;
    for(int i = LG; i >= 0; --i) {
        int k = (s >> i) & 1, t = child[u][k ^ 1];
        int x = lower_bound(save[t].begin(), save[t].end(), l) - save[t].begin(), y = upper_bound(save[t].begin(), save[t].end(), r) - save[t].begin() - 1;
        // auto x = lower_bound(save[t].begin(), save[t].end(), l)
        if(child[u][k ^ 1] != -1 && x <= y){
            u = child[u][k ^ 1];
            res += (1 << i);
        }else {
            u = child[u][k];
        }
    }
    cout << res << '\n';
}
void solve() {

    memset(child, -1, sizeof child);
    dfs(1, 0);
    ADD(0, 1);
    
    for(i = 1; i <= n; ++i) {
        auto [x, y] = query[i];
        if(type[i] == "Add") {
            ADD(Xor[x], y);
        }else {
            int now = Xor[x];
            get(now, in[y], out[y]);
        }
    }
}
int main() {

    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    add();
    solve();

}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 282012 KB Output is correct
2 Correct 54 ms 281716 KB Output is correct
3 Correct 54 ms 281680 KB Output is correct
4 Correct 59 ms 281684 KB Output is correct
5 Incorrect 57 ms 281776 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 282012 KB Output is correct
2 Correct 54 ms 281716 KB Output is correct
3 Correct 54 ms 281680 KB Output is correct
4 Correct 59 ms 281684 KB Output is correct
5 Incorrect 57 ms 281776 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 312180 KB Output is correct
2 Correct 392 ms 336696 KB Output is correct
3 Correct 431 ms 357812 KB Output is correct
4 Correct 502 ms 382460 KB Output is correct
5 Correct 338 ms 310064 KB Output is correct
6 Correct 367 ms 331860 KB Output is correct
7 Correct 444 ms 351252 KB Output is correct
8 Correct 482 ms 373420 KB Output is correct
9 Correct 355 ms 310200 KB Output is correct
10 Correct 378 ms 332664 KB Output is correct
11 Correct 429 ms 352712 KB Output is correct
12 Correct 480 ms 375348 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 282012 KB Output is correct
2 Correct 54 ms 281716 KB Output is correct
3 Correct 54 ms 281680 KB Output is correct
4 Correct 59 ms 281684 KB Output is correct
5 Incorrect 57 ms 281776 KB Output isn't correct
6 Halted 0 ms 0 KB -