Submission #637940

#	Time	Username	Problem	Language	Result	Execution time	Memory
637940		Iwanttobreakfree	Klasika (COCI20_klasika)	C++17	33 / 110	52 ms	13548 KiB

klasika

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int best=0;
vector<map<int,int>> trie(1);
void add(int u,int x){
    for(int i=30;i>=0;i--){
        if(trie[u].find(x&(1<<i))==trie[u].end()){
                map<int,int> mp;
                trie[u][x&(1<<i)]=trie.size();
                trie.push_back(mp);
        }
        u=trie[u][x&(1<<i)];
    }
}
int maxi(int u,int x){
    int ans=0;
    for(int i=30;i>=0;i--){
        int to=(x&(1<<i))^(1<<i);
        //cout<<to<<' ';
        if(trie[u].find(to)!=trie[u].end()){
            ans+=to;
            u=trie[u][to];
        }else u=trie[u][to^(1<<i)];
        //cout<<u<<' '<<i<<' '<<to<<'\n';
    }
    return ans;
}
int bin_jump_dist(int a,int dif,vector<vector<int>>& par,vector<vector<int>>& dist){
    int ans=0;
    for(int i=18;i>=0;i--){
        if(dif&(1<<i)){
            ans^=dist[a][i];
            a=par[a][i];
        }
    }
    return ans;
}
int bin_jump_node(int a,int dif,vector<vector<int>>& par,vector<vector<int>>& dist){
    int ans=0;
    for(int i=18;i>=0;i--){
        if(dif&(1<<i)){
            ans^=dist[a][i];
            a=par[a][i];
        }
    }
    return a;
}
int LCA(int x,int y,vector<vector<int>>& par,vector<vector<int>>& dist,vector<int>& depth){
    if(depth[x]>depth[y])swap(x,y);
    int ans=bin_jump_dist(y,depth[y]-depth[x],par,dist);
    y=bin_jump_node(y,depth[y]-depth[x],par,dist);
    //cout<<ans<<'\n';
    if(x==y)return ans;
    for(int i=18;i>=0;i--){
        if(par[x][i]!=par[y][i]){
            ans^=dist[x][i];
            ans^=dist[y][i];
            x=par[x][i];
            y=par[y][i];
        }
    }
    return ans^dist[x][0]^dist[y][0];
}
void dfs(int a,vector<vector<pair<int,int>>>& g,int cnt,int sol){
    best=max(best,cnt^sol);
    for(auto x:g[a]){
        dfs(x.first,g,cnt^x.second,sol);
    }
}
int main(){
    int q,x,y,sz=1;
    string s;
    vector<vector<int>> par(1,vector<int>(19));
    vector<vector<int>> w(1,vector<int>(19));
    vector<int> depth(1),root1(1);
    for(int i=0;i<19;i++)par[0][i]=0;
    vector<vector<pair<int,int>>> g(3000,vector<pair<int,int>>());
    add(0,0);
    cin>>q;
    for(int qu=0;qu<q;qu++){
        cin>>s>>x>>y;
        if(s=="Add"){
            x--;
            g[x].push_back({par.size(),y});
            depth.push_back(depth[x]+1);
            root1.push_back(y^root1[x]);
            add(0,root1.back());
            vector<int> parx(19),wx(19);
            wx[0]=y;
            parx[0]=x;
            for(int i=1;i<19;i++){
                parx[i]=par[parx[i-1]][i-1];
                wx[i]=w[parx[i-1]][i-1]^wx[i-1];
                //cout<<wx[i]<<' ';
            }
            //cout<<wx[0]<<'\n';
            par.push_back(parx);
            w.push_back(wx);

        }
        else{
            x--;y--;
            int sol=LCA(x,y,par,w,depth);
            best=sol;
            //cout<<sol<<'\n';
            if(q>2000)best=maxi(0,best);
            else dfs(y,g,0,sol);
            cout<<best<<'\n';
            //cout<<trie.size()<<'\n';
        }
    }
}

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:73:15: warning: unused variable 'sz' [-Wunused-variable]
   73 |     int q,x,y,sz=1;
      |               ^~

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