Submission #1113979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113979		12345678	Klasika (COCI20_klasika)	C++17	110 / 110	1195 ms	113228 KiB

klasika

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

int q, x, y, dp[nx], cur=1, t[nx], res[nx], sz[nx];
string s;
vector<int> d[nx];
vector<pair<int, int>> qrs[nx];

struct node
{
    int mn;
    node *l, *r;
    node(): mn(1e9), l(0), r(0){}
};
typedef node* pnode;
pnode rt[nx];

void add(int x, int u)
{
    if (!rt[x]) rt[x]=new node(), rt[x]->mn=0;
    pnode c=rt[x];
    for (int i=30; i>=0; i--)
    {
        if (dp[u]&(1<<i))
        {
            if (!c->r) c->r=new node();
            c=c->r;
            c->mn=min(c->mn, t[u]);
        }
        else
        {
            if (!c->l) c->l=new node();
            c=c->l;
            c->mn=min(c->mn, t[u]);
        }
    }
}

void dfsadd(int u, int p)
{
    add(p, u);
    for (auto v:d[u]) dfsadd(v, p);
}

void dfsdelete(pnode x)
{
    if (!x) return;
    dfsdelete(x->l);
    dfsdelete(x->r);
    delete x;
}

void solve(int u)
{
    sz[u]=1;
    pair<int, int> hv;
    for (auto v:d[u]) solve(v), sz[u]+=sz[v], hv=max(hv, {sz[v], v});
    if (hv.second) swap(rt[u], rt[hv.second]);
    for (auto v:d[u]) if (v!=hv.second) dfsdelete(rt[v]), dfsadd(v, u);
    add(u, u);
    for (auto [x, idx]:qrs[u])
    {
        int ans=0;
        pnode cur=rt[u];
        for (int i=0; i<=30; i++)
        {
            if (dp[x]&(1<<(30-i)))
            {
                if (cur->l&&cur->l->mn<=idx) ans+=(1<<(30-i)), cur=cur->l;
                else cur=cur->r; 
            }
            else
            {
                if (cur->r&&cur->r->mn<=idx) ans+=(1<<(30-i)), cur=cur->r;
                else cur=cur->l;
            }
        }
        res[idx]=ans;
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>q;
    for (int i=1; i<=q; i++)
    {
        cin>>s>>x>>y;
        res[i]=-1;
        if (s[0]=='A') dp[++cur]=dp[x]^y, d[x].push_back(cur), t[cur]=i;
        else qrs[y].push_back({x, i});
    }
    solve(1);
    for (int i=1; i<=q; i++) if (res[i]!=-1) cout<<res[i]<<'\n';
}

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