Submission #1203612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203612		Hanksburger	Klasika (COCI20_klasika)	C++20	110 / 110	2475 ms	123696 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
int a[200005], arr[200005], tin[200005], tout[200005], n=1, q, t, C=2000;
vector<pair<int, pair<int, int> > > vec;
vector<pair<int, int> > adj[200005];
struct bin
{
    bin *lc, *rc;
    short int ind;
    bin(int ind) : lc(0), rc(0), ind(ind) {}
} *root[105];
void update(bin *b, int x)
{
    if (!b->ind)
        return;
    if (x&(1<<(b->ind-1)))
    {
        if (!b->rc)
            b->rc=new bin(b->ind-1);
        update(b->rc, x);
    }
    else
    {
        if (!b->lc)
            b->lc=new bin(b->ind-1);
        update(b->lc, x);
    }
}
int query(bin *b, int x)
{
    if (!b->ind)
        return 0;
    if (x&(1<<(b->ind-1)))
    {
        if (b->lc)
            return (1<<(b->ind-1))^query(b->lc, x);
        return query(b->rc, x);
    }
    else
    {
        if (b->rc)
            return (1<<(b->ind-1))^query(b->rc, x);
        return query(b->lc, x);
    }
}
void dfs(int u)
{
    tin[u]=++t;
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first, w=adj[u][i].second;
        a[v]=a[u]^w;
        dfs(v);
    }
    tout[u]=t;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> q;
    for (int i=0; i<q; i++)
    {
        string str;
        int x, y;
        cin >> str >> x >> y;
        if (str=="Add")
        {
            adj[x].push_back({++n, y});
            vec.push_back({1, {n, y}});
        }
        else
            vec.push_back({0, {x, y}});
    }
    dfs(1);
    for (int i=2; i<=n; i++)
        arr[i]=-1;
    for (int i=0; i<q; i++)
    {
        if (vec[i].first)
        {
            int u=vec[i].second.first;
            arr[tin[u]]=a[u];
            if (!root[tin[u]/C])
                root[tin[u]/C]=new bin(31);
            update(root[tin[u]/C], a[u]);
        }
        else
        {
            int l=tin[vec[i].second.second], r=tout[vec[i].second.second], x=a[vec[i].second.first], mx=0;
            if ((l-1)/C+1>(r+1)/C)
            {
                for (int j=l; j<=r; j++)
                    mx=max(mx, x^arr[j]);
            }
            else
            {
                for (int j=l; j<((l-1)/C+1)*C; j++)
                    mx=max(mx, x^arr[j]);
                for (int j=(r+1)/C*C; j<=r; j++)
                    mx=max(mx, x^arr[j]);
                for (int j=(l-1)/C+1; j<(r+1)/C; j++)
                    if (root[j])
                        mx=max(mx, query(root[j], x));
            }
            cout << mx << '\n';
        }
    }
}

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