oj.uz

Submission #1088858

# Submission time Handle Problem Language Result Execution time Memory
1088858 2024-09-15T10:46:35 Z vladilius Klasika (COCI20_klasika) C++17
33 / 110
 47 ms 27384 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
const int lg = 31;

struct TR{
    struct node{
        int nt[2];
        node(){
            nt[0] = nt[1] = 0;
        }
    };
    vector<node> t;
    int cc;
    void init(){
        t.pb({});
        t.pb({});
        cc = 1;
    }
    void add(int x){
        int v = 1;
        for (int i = lg; i >= 0; i--){
            bool bit = (x >> i) & 1;
            if (!t[v].nt[bit]){
                t[v].nt[bit] = ++cc;
                t.pb({});
            }
            v = t[v].nt[bit];
        }
    }
    int get(int x){
        int out = 0, v = 1;
        for (int i = lg; i >= 0; i--){
            bool bit = (x >> i) & 1;
            if (t[v].nt[!bit]){
                v = t[v].nt[!bit];
                out += (1 << i);
                continue;
            }
            v = t[v].nt[bit];
        }
        return out;
    }
};

struct ST{
    vector<TR> t;
    int n;
    ST(int ns){
        n = ns;
        t.resize(4 * n);
        for (int i = 0; i < 4 * n; i++){
            t[i].init();
        }
    }
    void add(int v, int tl, int tr, int& p, int& x){
        t[v].add(x);
        if (tl == tr) return;
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            add(vv, tl, tm, p, x);
        }
        else {
            add(vv + 1, tm + 1, tr, p, x);
        }
    }
    void add(int p, int x){
        add(1, 1, n, p, x);
    }
    int get(int v, int tl, int tr, int& l, int& r, int& x){
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r){
            return t[v].get(x);
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        return max(get(vv, tl, tm, l, r, x), get(vv + 1, tm + 1, tr, l, r, x));
    }
    int get(int l, int r, int x){
        return get(1, 1, n, l, r, x);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int q, cc = 1; cin>>q;
    vector<arr3> qs;
    vector<pii> g[q + 1];
    bool ind = 1;
    for (int i = 1; i <= q; i++){
        string type; int x, y; cin>>type>>x>>y;
        if (type[0] == 'A'){
            cc++;
            g[x].pb({cc, y});
            qs.pb({0, x, cc});
        }
        else {
            if (y != 1) ind = 0;
            qs.pb({1, x, y});
        }
    }
    int n = cc;
    vector<int> tin(n + 1), tout(n + 1), d(n + 1);
    int timer = 0;
    function<void(int)> fill = [&](int v){
        tin[v] = ++timer;
        for (auto [i, w]: g[v]){
            d[i] = d[v] ^ w;
            fill(i);
        }
        tout[v] = timer;
    };
    fill(1);
    
    if (ind){
        TR T;
        T.add(0);
        for (auto [type, x, y]: qs){
            if (!type){
                T.add(d[y]);
            }
            else {
                cout<<T.get(d[x])<<"\n";
            }
        }
    }
    else {
        ST T(n);
        T.add(1, 0);
        for (auto [type, x, y]: qs){
            if (!type){
                T.add(tin[y], d[y]);
            }
            else {
                cout<<T.get(tin[y], tout[y], d[x])<<"\n";
            }
        }
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 1 ms 860 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 5 ms 1884 KB Output is correct
14 Correct 6 ms 3288 KB Output is correct
15 Correct 7 ms 4820 KB Output is correct
16 Correct 8 ms 6740 KB Output is correct
17 Correct 3 ms 1884 KB Output is correct
18 Correct 5 ms 3388 KB Output is correct
19 Correct 7 ms 4700 KB Output is correct
20 Correct 9 ms 6484 KB Output is correct
21 Correct 3 ms 1744 KB Output is correct
22 Correct 6 ms 3676 KB Output is correct
23 Correct 6 ms 4568 KB Output is correct
24 Correct 9 ms 6348 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 27384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 5 ms 1884 KB Output is correct
14 Correct 6 ms 3288 KB Output is correct
15 Correct 7 ms 4820 KB Output is correct
16 Correct 8 ms 6740 KB Output is correct
17 Correct 3 ms 1884 KB Output is correct
18 Correct 5 ms 3388 KB Output is correct
19 Correct 7 ms 4700 KB Output is correct
20 Correct 9 ms 6484 KB Output is correct
21 Correct 3 ms 1744 KB Output is correct
22 Correct 6 ms 3676 KB Output is correct
23 Correct 6 ms 4568 KB Output is correct
24 Correct 9 ms 6348 KB Output is correct
25 Runtime error 47 ms 27384 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -