Submission #885132

#	Time	Username	Problem	Language	Result	Execution time	Memory
885132		huynhyen1609	Klasika (COCI20_klasika)	C++14	110 / 110	2486 ms	423276 KiB

klasika

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define NAME "andteddy"
//#define int long long
#define ii pair<int,int>
#define i(x) array<int,x>
const int N=2e5;
int q,n,pre[N+5],cnt,in[N+5],out[N+5];
vector<i(3)>vec;
vector<ii>graph[N+5];
int getbit(int x,int i)
{
    return (x>>i)&1;
}
void dfs(int u)
{
    in[u]=++cnt;
    for(ii v:graph[u])
    {
        pre[v.fi]=pre[u]^v.se;
        dfs(v.fi);
    }
    out[u]=cnt;
}
struct ta
{
    int c[2];
    set<int>s;
}trie[3000000];
void add(int u)
{
    int id=0;
    for(int i=30;i>=0;--i)
    {
        int tmp=getbit(pre[u],i);
        if(!trie[id].c[tmp])trie[id].c[tmp]=++cnt;
        id=trie[id].c[tmp];
        trie[id].s.insert(in[u]);
    }
}
int get(int u,int v)
{
    int id=0,res=pre[u];
    for(int i=30;i>=0;--i)
    {
        int t=0;
        int tmp=getbit(pre[u],i);
        if(trie[id].c[tmp^1])
        {
            int tm=trie[id].c[tmp^1];
            int l=*trie[tm].s.lower_bound(in[v]);
            if(l>=in[v]&&l<=out[v])
            {
                id=trie[id].c[tmp^1];
                res^=(tmp^1)<<i;
                t=1;
            }
        }
        if(trie[id].c[tmp]&&t!=1)
        {
            int tm=trie[id].c[tmp];
            int l=*trie[tm].s.lower_bound(in[v]);
            if(l>=in[v]&&l<=out[v])
            {
                id=trie[id].c[tmp];
                res^=tmp<<i;
            }
        }
    }
    return res;
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    //freopen(""NAME".inp","r",stdin);
    //freopen(""NAME".out","w",stdout);
    cin>>q;
    n=1;
    for(int i=1;i<=q;++i)
    {
        string s;
        int u,v;
        cin>>s;
        cin>>u>>v;
        if(s=="Add")
        {
            vec.push_back({0,++n,0});
            graph[u].push_back({n,v});
        }
        else
        {
            vec.push_back({1,u,v});
        }
    }
    dfs(1);
    cnt=0;
    add(1);
    for(i(3)x:vec)
    {
        if(!x[0])add(x[1]);
        else cout<<get(x[1],x[2])<<'\n';
    }
}
/*
         ଘ(੭ˊᵕˋ)੭* ੈ✩‧˚huynhyen1609<3
*/

Compilation message (stderr)

klasika.cpp:74:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 | main()
      | ^~~~

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