제출 #1306605

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306605		DangKhoizzzz	Klasika (COCI20_klasika)	C++20	110 / 110	612 ms	193164 KiB

klasika

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair <int , int>
#define BIT(x, k) ((x >> k) & 1)

using namespace std;

const int maxn = 2e5 + 7;
const int MAX_NODES = maxn * 32; 

struct info 
{
    string t;
    int c1, c2;
} query[maxn]; 

struct node
{
    int c[2];
    vector<pair<int, int>> pos; 
    
    node() {
        c[0] = c[1] = -1; 
    }
};

vector<node> trie;

void init_trie() {
    trie.reserve(MAX_NODES); 
    trie.push_back(node());
}

void add(int x, int p, int time_id)
{
    int cur = 0;
    trie[cur].pos.push_back({p, time_id}); 
    for(int i = 30; i >= 0; i--)
    {
        int b = BIT(x, i);
        if(trie[cur].c[b] == -1) 
        {
            trie[cur].c[b] = trie.size();
            trie.push_back(node());
        }
        cur = trie[cur].c[b];
        trie[cur].pos.push_back({p, time_id});
    }
}

bool check(const vector<pair<int,int>>& v, int l, int r, int current_time) {
    auto it = lower_bound(v.begin(), v.end(), make_pair(l, -1));
    for (; it != v.end() && it->first <= r; ++it) {
        if (it->second <= current_time) return true;
    }
    return false;
}

int ask(int x, int l, int r, int current_time)
{
    int res = 0, cur = 0;
    for(int i = 30; i >= 0; i--)
    {
        int f = (1 ^ BIT(x, i)); 
        int cf = trie[cur].c[f];
        if(cf != -1 && !trie[cf].pos.empty() && check(trie[cf].pos, l, r, current_time))
        {
            res ^= (1 << i);
            cur = cf;
        }
        else {
            cur = trie[cur].c[f ^ 1];
            if (cur == -1) return res; 
        }
    }
    return res;
}

int pre[maxn], q, n = 1, tin[maxn], tout[maxn], time_dfs = 0;
vector <int> g[maxn];

void dfs(int u)
{
    tin[u] = ++time_dfs;
    for(int v: g[u]) dfs(v);     
    tout[u] = time_dfs;
}

void solve()
{
    cin >> q;
    vector<tuple<int, int, int>> add_ops; 
    for(int i = 1; i <= q; i++)
    {
        cin >> query[i].t >> query[i].c1 >> query[i].c2;
        if(query[i].t == "Add")
        {
            auto [t, x, y] = query[i];
            n++;
            g[x].push_back(n);
            pre[n] = (pre[x] ^ y);
            add_ops.emplace_back(n, i, pre[n]); 
        }
    }
    dfs(1);
    init_trie();
    add(0, tin[1], 0); 
    for(auto& op : add_ops) {
        add(get<2>(op), tin[get<0>(op)], get<1>(op));
    }
    for(auto &node : trie) {
        sort(node.pos.begin(), node.pos.end());
    }
    int cnt_add = 0; 
    for(int i = 1; i <= q; i++)
    {
        if(query[i].t == "Add") 
        {

        }
        else 
        {
            cout << ask(pre[query[i].c1], tin[query[i].c2], tout[query[i].c2], i) << '\n';
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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