oj.uz

답안 #1088873

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1088873 2024-09-15T11:46:13 Z vladilius Klasika (COCI20_klasika) C++17
0 / 110
 201 ms 94736 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;
const int S = 2500;

struct FT{
    vector<int> bit;
    int n;
    void init(int ns){
        n = ns;
        bit.resize(n + 1);
    }
    void add(int v, int x){
        while (v <= n){
            bit[v] += x;
            v |= (v + 1);
        }
    }
    int get(int v){
        int out = 0;
        while (v > 0){
            out += bit[v];
            v = (v & (v + 1)) - 1;
        }
        return out;
    }
    int get(int l, int r){
        return get(r) - get(l - 1);
    }
};

struct TR{
    struct node{
        vector<int> all;
        int nt[2];
        node(){
            nt[0] = nt[1] = 0;
        }
    };
    vector<node> t;
    vector<int> g;
    FT T[100];
    int cc, n, cc1 = 0;
    void init(int ns, int q){
        t.pb({});
        t.pb({});
        cc = 1;
        cc1 = 0;
        n = ns;
        g.resize(q * lg + 1);
    }
    vector<int> :: iterator it;
    void add(int x, int p){
        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];
            t[v].all.pb(p);
            if (t[v].all.size() >= S){
                if (!g[v]){
                    g[v] = ++cc1;
                    T[cc1].init(n);
                    for (int i: t[v].all){
                        T[cc1].add(i, 1);
                    }
                    continue;
                }
                T[g[v]].add(p, 1);
            }
        }
    }
    int get(int l, int r, int x){
        int out = 0, v = 1;
        for (int i = lg; i >= 0; i--){
            bool bit = (x >> i) & 1;
            int k = t[v].nt[!bit];
            if (k > 0){
                bool ind = 0;
                if (t[k].all.size() < S){
                    for (int i: t[k].all){
                        if (l <= i && i <= r){
                            ind = 1;
                            break;
                        }
                    }
                }
                else {
                    ind = (T[g[v]].get(l, r) > 0);
                }
                if (ind){ 
                    v = k;
                    out += (1 << i);
                    continue;
                }
            }
            v = t[v].nt[bit];
        }
        return out;
    }
};

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);

    TR T; T.init(n, q);
    for (auto [type, x, y]: qs){
        if (!type){
            T.add(d[y], tin[y]);
        }
        else {
            cout<<T.get(tin[y], tout[y], d[x])<<"\n";
        }
    }
}

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:120:10: warning: variable 'ind' set but not used [-Wunused-but-set-variable]
  120 |     bool ind = 1;
      |          ^~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 201 ms 94736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -