제출 #1306613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306613		DangKhoizzzz	Klasika (COCI20_klasika)	C++20	110 / 110	605 ms	248608 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];
    vector <pii> pos;
    node() {c[0] = c[1] = -1; }
};
vector <node> trie;

void add(int x , int p , int time)
{
    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.push_back({p , time});
    }
}

bool check(int cur , int l , int r , int time)
{
    auto st = lower_bound(trie[cur].pos.begin() , trie[cur].pos.end() , (pii){l , -1});
    for(; st < trie[cur].pos.end() && st->fi <= r; st++)
    {
        if(st->se <= time) return true;
    }
    return false;
}

int ask(int x , int l , int r , int 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 && check(cf , l , r , time))
        {
            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)
{
    tin[u] = ++time_dfs;
    for(int v: g[u]) dfs(v);     
    tout[u] = time_dfs;
}
void solve()
{
    cin >> q;
    trie.push_back(node());
    vector <arr3> add_op = {{0 , 1 , 0}};
    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_op.push_back({pre[n] , n , i});
        }
    }
    dfs(1);
    for(auto [x , y , z]: add_op) add(x , tin[y] , z);
    for(auto &tmp: trie) sort(tmp.pos.begin() , tmp.pos.end()); 
    for(int i = 1 , cnt = 1; i <= q; i++)
    {
        if(query[i].t == "Query") 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