oj.uz

Submission #857080

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

#define fi first
#define se second

const int N = 3e6 + 10;
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;

        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 55 ms 263312 KB Output is correct
2 Correct 53 ms 263336 KB Output is correct
3 Correct 56 ms 263252 KB Output is correct
4 Correct 51 ms 263772 KB Output is correct
5 Incorrect 50 ms 263252 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 263312 KB Output is correct
2 Correct 53 ms 263336 KB Output is correct
3 Correct 56 ms 263252 KB Output is correct
4 Correct 51 ms 263772 KB Output is correct
5 Incorrect 50 ms 263252 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 303 ms 295500 KB Output is correct
2 Correct 448 ms 321584 KB Output is correct
3 Correct 418 ms 344464 KB Output is correct
4 Correct 455 ms 369328 KB Output is correct
5 Correct 295 ms 296556 KB Output is correct
6 Correct 441 ms 318528 KB Output is correct
7 Correct 426 ms 337832 KB Output is correct
8 Correct 522 ms 360196 KB Output is correct
9 Correct 288 ms 296520 KB Output is correct
10 Correct 400 ms 319164 KB Output is correct
11 Correct 405 ms 339144 KB Output is correct
12 Correct 454 ms 361784 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 263312 KB Output is correct
2 Correct 53 ms 263336 KB Output is correct
3 Correct 56 ms 263252 KB Output is correct
4 Correct 51 ms 263772 KB Output is correct
5 Incorrect 50 ms 263252 KB Output isn't correct
6 Halted 0 ms 0 KB -