제출 #1098602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098602		hiensumi	Klasika (COCI20_klasika)	C++14	33 / 110	5088 ms	173736 KiB

klasika

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

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]) i = trie[i][1];
            else{
                sort(all(ids[trie[i][0]]));
                if(lower_bound(all(ids[trie[i][0]]), l) == upper_bound(all(ids[trie[i][0]]), r)){
                    i = trie[i][1];
                    continue;
                }
                res += mask(j);
                i = trie[i][0];
            }
        }
        else{
            if(!trie[i][1]) i = trie[i][0];
            else{
                sort(all(ids[trie[i][1]]));
                if(lower_bound(all(ids[trie[i][1]]), l) == upper_bound(all(ids[trie[i][1]]), r)){
                    i = trie[i][0];
                    continue;
                }
                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 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44