oj.uz

Submission #1098597

# Submission time Handle Problem Language Result Execution time Memory
1098597 2024-10-09T16:03:33 Z hiensumi Klasika (COCI20_klasika) C++14
33 / 110
 491 ms 273336 KB 
#include <bits/stdc++.h>
using namespace std;
#define fod(i,a,b) for(int i = (int) (a); i <= (int) (b); i++)
#define fok(i,a,b) for(int i = (int) (a); i >= (int) (b); i--)
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define el '\n'
#define ve vector
#define vi ve<int>
#define vll ve<ll>
#define mask(a) (1LL<<(a))
#define BIT(msk,i) (msk>>(i)&1LL)
using namespace std;
template <class T> bool mini(T &a, T b){ return (a > (b)) ? a = (b), 1 : 0; }
template <class T> bool maxi(T &a, T b){ return (a < (b)) ? a = (b), 1 : 0; }
#define name "klasika"

int n = 1, q;

const int N = 2e5;

struct Query{
    bool new_node;
    int x, y;
}query[N + 5];

ve <ve<pii>> g;

int in[N + 5], out[N + 5], timedfs = 0;
int f[N + 5];

void dfs(int u, int p){
    in[u] = ++timedfs;
    for(pii who : g[u]) if(who.fi != p){
        int v, w; tie(v, w) = who;
        f[v] = f[u] xor w;
        dfs(v, u);
    }
    out[u] = timedfs;
}

int num_node = 1, trie[31 * N + 5][2];
vi ids[31 * N + 5];

#define all(a) a.begin(), a.end()
inline void add(int val, int id){
    int i = 1;
    fok(j,30,0){
        int w = BIT(val, j);
        if(!trie[i][w]) trie[i][w] = ++num_node;
        i = trie[i][w];
        ids[i].pb(id);
//        sort(all(ids[i]));
    }
}

int get(int val, int l, int r){
    int i = 1;
    int res = 0;

    fok(j,30,0){
        if(BIT(val, j)){
            if(!trie[i][0] or lower_bound(all(ids[trie[i][0]]), l) == upper_bound(all(ids[trie[i][0]]), r)) i = trie[i][1];
            else{
                res += mask(j);
                i = trie[i][0];
            }
        }
        else{
            if(!trie[i][1] or lower_bound(all(ids[trie[i][1]]), l) == upper_bound(all(ids[trie[i][1]]), r)) i = trie[i][0];
            else{
                res += mask(j);
                i = trie[i][1];
            }
        }
    }

    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
  
    cin >> q;

    g.resize(q + 1);

    fod(i,1,q){
        string s; cin >> s;
        int x, y; cin >> x >> y;

        if(s == "Add"){
            n++;
            g[x].pb(mp(n, y));
            g[n].pb(mp(x, y));
            query[i] = Query{1, n, y};
        }
        else query[i] = Query{0, x, y};
    }

    dfs(1, 0);

    add(f[1], in[1]);

    fod(i,1,q){
        if(query[i].new_node){
            add(f[query[i].x], in[query[i].x]);
        }
        else{
            cout << get(f[query[i].x], in[query[i].y], out[query[i].y]) << el;
        }
    }

    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 145936 KB Output is correct
2 Correct 56 ms 146000 KB Output is correct
3 Correct 54 ms 146112 KB Output is correct
4 Correct 54 ms 146000 KB Output is correct
5 Incorrect 53 ms 146000 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 145936 KB Output is correct
2 Correct 56 ms 146000 KB Output is correct
3 Correct 54 ms 146112 KB Output is correct
4 Correct 54 ms 146000 KB Output is correct
5 Incorrect 53 ms 146000 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 284 ms 188112 KB Output is correct
2 Correct 371 ms 218404 KB Output is correct
3 Correct 436 ms 244464 KB Output is correct
4 Correct 468 ms 273336 KB Output is correct
5 Correct 323 ms 187084 KB Output is correct
6 Correct 413 ms 214036 KB Output is correct
7 Correct 487 ms 237796 KB Output is correct
8 Correct 490 ms 264344 KB Output is correct
9 Correct 297 ms 187188 KB Output is correct
10 Correct 425 ms 214600 KB Output is correct
11 Correct 490 ms 239120 KB Output is correct
12 Correct 491 ms 265992 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 145936 KB Output is correct
2 Correct 56 ms 146000 KB Output is correct
3 Correct 54 ms 146112 KB Output is correct
4 Correct 54 ms 146000 KB Output is correct
5 Incorrect 53 ms 146000 KB Output isn't correct
6 Halted 0 ms 0 KB -