제출 #1306594

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

klasika

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

using namespace std;

const int maxn = 2e5 + 7;
const int INF = 1e9;

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

struct node
{
    int c[2];
    set <int> pos;
    node() {c[0] = c[1] = -1; pos.insert(INF);}
};
vector <node> trie;

void add(int x , int p)
{
    int cur = 0;
    for(int i = 30; i >= 0; i--)
    {
        if(trie[cur].c[BIT(x , i)] == -1) 
        {
            trie[cur].c[BIT(x , i)] = trie.size();
            trie.push_back(node());
        }
        cur = trie[cur].c[BIT(x , i)];
        trie[cur].pos.insert(p);
    }
}
int ask(int x , int l , int r)
{
    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() && *trie[cf].pos.lower_bound(l) <= r)
        {
            res ^= (1 << i);
            cur = cf;
        }
        else cur = trie[cur].c[f^1];
    }
    return res;
}

int pre[maxn] , q , n = 1 , tin[maxn] , tout[maxn] , time_dfs = 0;
vector <int> g[maxn];
void dfs(int u , int p)
{
    tin[u] = ++time_dfs;
    for(int v: g[u]) dfs(v , u);     
    tout[u] = ++time_dfs;
}
void solve()
{
    cin >> q;
    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);
        }
    }
    trie.push_back(node());
    dfs(1 , 1);
    add(0 , 1);
    for(int i = 1 , cnt = 1; i <= q; i++)
    {
        if(query[i].t == "Add")
        {
            auto [t , x , y] = query[i]; cnt++;
            add(pre[cnt] , tin[cnt]);
        }
        else
        {
            auto [t , a , b] = query[i]; cout << ask(pre[a] , tin[b] , tout[b]) << '\n';
        }
    }
}
signed 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: 0 / 33
• Subtask 4: 0 / 44