oj.uz

Submission #1098587

# Submission time Handle Problem Language Result Execution time Memory
1098587 2024-10-09T15:56:10 Z hiensumi Klasika (COCI20_klasika) C++14
33 / 110
 1418 ms 524288 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[30 * N + 5][2];
set <int> ids[30 * N + 5];

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].insert(id);
    }
}

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 ids[trie[i][0]].lower_bound(l) == ids[trie[i][0]].upper_bound(r)) i = trie[i][1];
            else{
                res += mask(j);
                i = trie[i][0];
            }
        }
        else{
            if(!trie[i][1] or ids[trie[i][1]].lower_bound(l) == ids[trie[i][1]].upper_bound(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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 282192 KB Output is correct
2 Correct 117 ms 282196 KB Output is correct
3 Correct 120 ms 282456 KB Output is correct
4 Correct 116 ms 282452 KB Output is correct
5 Correct 126 ms 282332 KB Output is correct
6 Correct 120 ms 282192 KB Output is correct
7 Correct 116 ms 282436 KB Output is correct
8 Correct 117 ms 282448 KB Output is correct
9 Correct 118 ms 282292 KB Output is correct
10 Correct 118 ms 282280 KB Output is correct
11 Correct 118 ms 282452 KB Output is correct
12 Correct 119 ms 282448 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 282192 KB Output is correct
2 Correct 117 ms 282196 KB Output is correct
3 Correct 120 ms 282456 KB Output is correct
4 Correct 116 ms 282452 KB Output is correct
5 Correct 126 ms 282332 KB Output is correct
6 Correct 120 ms 282192 KB Output is correct
7 Correct 116 ms 282436 KB Output is correct
8 Correct 117 ms 282448 KB Output is correct
9 Correct 118 ms 282292 KB Output is correct
10 Correct 118 ms 282280 KB Output is correct
11 Correct 118 ms 282452 KB Output is correct
12 Correct 119 ms 282448 KB Output is correct
13 Correct 128 ms 282960 KB Output is correct
14 Correct 124 ms 283756 KB Output is correct
15 Correct 123 ms 284496 KB Output is correct
16 Correct 129 ms 285008 KB Output is correct
17 Correct 127 ms 282968 KB Output is correct
18 Correct 113 ms 283476 KB Output is correct
19 Correct 107 ms 284340 KB Output is correct
20 Correct 111 ms 284944 KB Output is correct
21 Correct 107 ms 282964 KB Output is correct
22 Correct 108 ms 283632 KB Output is correct
23 Correct 110 ms 284288 KB Output is correct
24 Correct 112 ms 285012 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 360528 KB Output is correct
2 Correct 1074 ms 427588 KB Output is correct
3 Correct 1418 ms 493140 KB Output is correct
4 Runtime error 1257 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 282192 KB Output is correct
2 Correct 117 ms 282196 KB Output is correct
3 Correct 120 ms 282456 KB Output is correct
4 Correct 116 ms 282452 KB Output is correct
5 Correct 126 ms 282332 KB Output is correct
6 Correct 120 ms 282192 KB Output is correct
7 Correct 116 ms 282436 KB Output is correct
8 Correct 117 ms 282448 KB Output is correct
9 Correct 118 ms 282292 KB Output is correct
10 Correct 118 ms 282280 KB Output is correct
11 Correct 118 ms 282452 KB Output is correct
12 Correct 119 ms 282448 KB Output is correct
13 Correct 128 ms 282960 KB Output is correct
14 Correct 124 ms 283756 KB Output is correct
15 Correct 123 ms 284496 KB Output is correct
16 Correct 129 ms 285008 KB Output is correct
17 Correct 127 ms 282968 KB Output is correct
18 Correct 113 ms 283476 KB Output is correct
19 Correct 107 ms 284340 KB Output is correct
20 Correct 111 ms 284944 KB Output is correct
21 Correct 107 ms 282964 KB Output is correct
22 Correct 108 ms 283632 KB Output is correct
23 Correct 110 ms 284288 KB Output is correct
24 Correct 112 ms 285012 KB Output is correct
25 Correct 652 ms 360528 KB Output is correct
26 Correct 1074 ms 427588 KB Output is correct
27 Correct 1418 ms 493140 KB Output is correct
28 Runtime error 1257 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -