Submission #1291320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291320		huypham2009	Klasika (COCI20_klasika)	C++20	110 / 110	736 ms	140712 KiB

klasika

#include <iostream>
#include <cmath>
#include <climits>
#include <vector>
using namespace std;
const int LOG=29;
const int maxn=2e5+5;
struct node{
    node *child[2];
    int last,cnt;
    bool endd;
    node()
    {
        child[0]=NULL;
        child[1]=NULL;
        last=INT_MAX;
        cnt=0;
    }
};
struct Trie{
    node *root;
    Trie()
    {
        root=new node();
    }
    void add(int x,int t)
    {
        node *cur=root;
        root->cnt++;
        for(int i=LOG;i>=0;i--)
        {
            bool c=x&(1<<i);
            if(!cur->child[c])  cur->child[c]=new node();
            cur=cur->child[c];
            cur->last=min(cur->last,t);
        }
    }
    void add(node *&cur,node *&copy)
    {
        if(cur==NULL)   cur=new node();
        cur->last=min(cur->last,copy->last);
        cur->endd=max(cur->endd,copy->endd);
        if(copy->child[0])
        {
            add(cur->child[0],copy->child[0]);
        }
        if(copy->child[1])
        {
            add(cur->child[1],copy->child[1]);
        }
        delete(copy);
    }
    void add(Trie &a)
    {
        root->cnt+=a.root->cnt;
        add(root,a.root);
        a.root=NULL;
    }
    int Find(int x,int t)
    {
        node *cur=root;
        int res=0,best=x;
        for(int i=LOG;i>=0;i--)
        {
            bool c=x&(1<<i);
            if(cur->child[c^1]!=NULL&&cur->child[c^1]->last<=t)
            {
                res+=((c^1)<<i);
                cur=cur->child[c^1];
            }
            else if(cur->child[c]!=NULL&&cur->child[c]->last<=t)
            {
                res+=(c<<i);
                cur=cur->child[c];
            }
        }
        return res;
    }

} ;
vector<Trie>trie;
//t,subroot,time
struct Query{
    int q,times,d;
};
vector<Query>Q[maxn];
int cnt,n=1,q,xoru[maxn],ans[maxn],buildtime[maxn];
vector<int>g[maxn];
void Swap(Trie &a,Trie &b)
{
    swap(a.root,b.root);
}
void dfs(int u)
{
    for(int v:g[u])
    {
        dfs(v);
        if(trie[u].root->cnt<trie[v].root->cnt) Swap(trie[u],trie[v]);
        trie[u].add(trie[v]);
    }
    trie[u].add(xoru[u],buildtime[u]);
    for(Query x:Q[u])
    {
        ans[x.q]=trie[u].Find(x.d,x.times)^x.d;
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        string s;
        cin>>s;
        if(s=="Add")
        {
            int x,y;
            cin>>x>>y;
            xoru[++n]=xoru[x]^y;
            buildtime[n]=i;
            g[x].push_back(n);
        }
        else
        {
            int a,b;
            cin>>a>>b;
            Q[b].push_back({++cnt,i,xoru[a]});
        }
    }
    trie.resize(n+1);
    dfs(1);
    for(int i=1;i<=cnt;i++) cout<<ans[i]<<'\n';
    return 0;
}

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