Submission #1203557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203557		Hanksburger	Klasika (COCI20_klasika)	C++20	33 / 110	855 ms	589824 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
int a[200005], tin[200005], tout[200005], n=1, q, t;
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) {}
};
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);
    }
}
struct node
{
    node *lc, *rc;
    int l, r, sz;
    bin *b;
    int *v;
    node(int l, int r) : lc(0), rc(0), l(l), r(r), sz(0), b(0), v(0) {}
} *root;
void build(node *i)
{
    if (i->l==i->r)
        return;
    int mid=(i->l+i->r)/2;
    build(i->lc=new node(i->l, mid));
    build(i->rc=new node(mid+1, i->r));
}
void update(node *i, int x, int y)
{
    //cout << "update " << i->l << ' ' << i->r << ' ' << x << ' ' << y << '\n';
    if (i->b)
        update(i->b, y);
    else if (!i->v)
    {
        i->v=new int[50];
        i->v[0]=y;
        i->sz++;
    }
    else if (i->sz<50)
    {
        i->v[i->sz]=y;
        i->sz++;
    }
    else if (i->sz==50)
    {
        i->b=new bin(31);
        for (int j=0; j<50; j++)
            update(i->b, i->v[j]);
        update(i->b, y);
        delete i->v;
    }
    if (i->l==i->r)
        return;
    int mid=(i->l+i->r)/2;
    if (x<=mid)
        update(i->lc, x, y);
    else
        update(i->rc, x, y);
}
int query(node *i, int ql, int qr, int x)
{
    //cout << "query " << i->l << ' ' << i->r << ' ' << ql << ' ' << qr << ' ' << x << '\n';
    if (ql<=i->l && i->r<=qr)
    {
        if (i->b)
            return query(i->b, x);
        if (!i->v)
            return -1;
        int mx=0;
        for (int j=0; j<i->sz; j++)
            mx=max(mx, x^i->v[j]);
        return mx;
    }
    int mid=(i->l+i->r)/2, mx=0;
    if (i->l<=qr && ql<=mid)
        mx=max(mx, query(i->lc, ql, qr, x));
    if (mid<qr && ql<=i->r)
        mx=max(mx, query(i->rc, ql, qr, x));
    return mx;
}
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);
    build(root=new node(1, n));
    update(root, 1, 0);
    for (int i=0; i<q; i++)
    {
        if (vec[i].first)
            update(root, tin[vec[i].second.first], a[vec[i].second.first]);
        else
            cout << query(root, tin[vec[i].second.second], tout[vec[i].second.second], a[vec[i].second.first]) << '\n';
    }
}

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