oj.uz

답안 #857084

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -