제출 #1125165

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125165		baotoan655	Klasika (COCI20_klasika)	C++17	110 / 110	719 ms	355920 KiB

klasika

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define REV(i, a, b) for(int i = (a); i >= (b); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define fi first
#define se second

using namespace std;

const int N = 2e5 + 5;

struct node {
    int child[2];
    int mn;
    node() {
        child[0] = child[1] = -1;
        mn = (int)1e9;
    }
};
struct trie {
    vector<node> nod;
    vector<pair<int, int>> ve;
    void init() {
        nod.clear();
        nod.push_back(node());
        ve.clear();
    }
    trie() {
        init();
    }
    int size() {return (int)ve.size();}
    void add(int val, int t) {
        ve.emplace_back(val, t);
        int cur = 0;
        for(int i = 30; i >= 0; --i) {
            int c = val >> i & 1;
            if(nod[cur].child[c] == -1) {
                nod[cur].child[c] = nod.size();
                nod.push_back(node());
            }
            cur = nod[cur].child[c];
            nod[cur].mn = min(nod[cur].mn, t);
        }
    }
    int query(int val, int t) {
        int cur = 0, res = 0;
        for(int i = 30; i >= 0; --i) {
            int c = val >> i & 1;
            if(nod[cur].child[c ^ 1] != -1 && nod[nod[cur].child[c ^ 1]].mn <= t) {
                res |= (1 << i);
                cur = nod[cur].child[c ^ 1];
            } else {
                if(nod[cur].child[c] != -1 && nod[nod[cur].child[c]].mn <= t) {
                    cur = nod[cur].child[c];
                } else return 0;
            }
        }
        return res;
    }
} tree[N];
int q;
int n;
int pref[N];
int ans[N];
vector<pair<int, int>> g[N], query[N];

void dfs(int u) {
    for(auto [v, w] : g[u]) {
        dfs(v);
        if(tree[u].size() < tree[v].size()) swap(tree[u], tree[v]);
        for(auto [val, t] : tree[v].ve) {
            tree[u].add(val, t);
        }
    }
    for(auto [val, id] : query[u]) {
        ans[id] = tree[u].query(val, id);
    }
}

void solve(int tc) {
    memset(ans, -1, sizeof ans);
    cin >> q;
    n = 1;
    tree[1].init();
    tree[1].add(0, 0);
    FOR(i, 1, q) {
        string str;
        int x, y;
        cin >> str >> x >> y;
        if(str[0] == 'A') {
            g[x].emplace_back(++n, y);
            pref[n] = pref[x] ^ y;
            tree[n].init();
            tree[n].add(pref[n], i);
        } else {
            query[y].emplace_back(pref[x], i);
        }
    }
    dfs(1);
    FOR(i, 1, q) {
        if(ans[i] != -1) cout << ans[i] << '\n';
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("A.inp", "r", stdin);
//    freopen("A.out", "w", stdout);
    int tc = 1;
//    cin >> tc;
    FOR(_, 1, tc) solve(tc);
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44