Submission #769568

#	Time	Username	Problem	Language	Result	Execution time	Memory
769568		vjudge1	Klasika (COCI20_klasika)	C++17	66 / 110	908 ms	524288 KiB

klasika

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define ss second
#define ff first
#define all(x) (x).begin(), (x).end()

const int nax = 2e5 + 4;
int q, n = 1, k = 1;
int d[nax], eul[nax], eulend[nax];
int cureul = -1;
vector<pii> adj[nax];
struct node
{
    char layer = 0;
    node *zer, *one;
    node(): layer(0), zer(nullptr), one(nullptr){}
    node (char d, node *ll, node *rr)
    {
        zer = ll, one = rr;
        layer= d;
    }
    node(node *cp): layer(cp->layer), zer(cp->zer), one(cp->one) {}
};
node *update(node *Node, int val, char d)
{
    if(d == 0)
        return new node();
    if(val & (1 << (d - 1)))
    {
        if(Node->one == nullptr)
            Node->one = new node(d - 1, nullptr, nullptr);
        return new node(d, Node->zer, update(Node->one, val, d - 1));

    }
    else
    {
        if(Node->zer == nullptr)
            Node->zer = new node(d - 1, nullptr, nullptr);
        return new node(d, update(Node->zer, val, d - 1), Node->one);
    }
}
node *roots[4 * nax];

int query(node *Node, int val)
{

    if(Node->layer == 0)
        return 0;
   // cout << Node->layer << ' ' << val << '\n';
    if(val & (1 << (Node->layer - 1)))
    {
        if(Node->zer != nullptr)
            return (1 << (Node->layer - 1)) + query(Node->zer, val);
        else
            return query(Node->one, val);
    }
    else
    {
        if(Node->one != nullptr)
            return (1 << (Node->layer - 1)) + query(Node->one, val);
        else
            return query(Node->zer, val);
    }
}
void pupd(int i, int val)
{
    i += k;
    if(roots[i] == nullptr)
        roots[i] = new node(30, nullptr, nullptr);
    roots[i] = update(roots[i], val, 30);
   // cout << i << endl;
    i /= 2;

    while(i)
    {
        //cout << i << endl;
        if(roots[i] == nullptr)
        roots[i] = new node(30, nullptr, nullptr);
        roots[i] = update(roots[i], val, 30);
        i /= 2;
    }
}
int squery(int p, int l, int r, int i, int j, int val)
{
    if(i > j)
        return 0;
    if(l >= i && r <= j)
    {
        if(roots[p] != nullptr)
            return query(roots[p], val);
        else
            return 0;
    }
    int m = (l + r)/2;
    return max(squery(2 * p, l, m, i, min(j, m), val),
               squery(2 * p + 1, m + 1, r, max(i, m + 1), j, val));
}
void dfs(int x, int p)
{
    eul[x] = ++cureul;
    for(auto e: adj[x])
    {
        d[e.ff] = d[x]^e.ss;
        dfs(e.ff, x);
    }
    eulend[x] = cureul;
}
void solve()
{
    cin >> q;
    vector<pair<int,pii>>  queries;
    bool flag= true;
    for(int i = 1; i <= q; i++)
    {
        string s; cin >> s;
        int x, y;
        cin >> x >> y;
        if(s== "Add")
        {
            adj[x].pb({++n, y});
            x = n;
        }
        else
        {
            flag &= (y == 1);
        }
        queries.pb({(s == "Query"), {x, y}});
    }

    dfs(1, 0);

    while(k < n)
        k = (k << 1);
    //bbuild(1, 0, k - 1);
    pupd(0, 0);
   // cout << squery(1, 0, k - 1, eul[1], eulend[1], d[1]) << '\n';
    for(auto e: queries)
    {
        if(flag)
        {
            if(e.ff == 0)
            {
                //cout << e.ss.ff << ' ' << eul[e.ss.ff] << endl;
                update(roots[1], d[e.ss.ff], 30);
            }
            else
            {
                int a = e.ss.ff;
                int b = e.ss.ss;
               // cout << a << ' ' << b << endl;
                cout << query(roots[1], d[a]) << '\n';
            }
        }
        else
        {
            if(e.ff == 0)
            {
                //cout << e.ss.ff << ' ' << eul[e.ss.ff] << endl;
                pupd(eul[e.ss.ff], d[e.ss.ff]);
            }
            else
            {
                int a = e.ss.ff;
                int b = e.ss.ss;
               // cout << a << ' ' << b << endl;
                cout << squery(1, 0, k - 1, eul[b], eulend[b], d[a]) << '\n';
            }
        }
    }
}
int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tt = 1;
    while(tt--)
        solve();
}

Compilation message (stderr)

klasika.cpp: In function 'void solve()':
klasika.cpp:159:21: warning: unused variable 'b' [-Wunused-variable]
  159 |                 int b = e.ss.ss;
      |                     ^

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