Submission #637924

#	Time	Username	Problem	Language	Result	Execution time	Memory
637924		Iwanttobreakfree	Klasika (COCI20_klasika)	C++17	33 / 110	152 ms	2980 KiB

klasika

#include <iostream>
#include <vector>
using namespace std;
int best=0;
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);
    for(int i=0;i<19;i++)par[0][i]=0;
    vector<vector<pair<int,int>>> g(3000,vector<pair<int,int>>());
    cin>>q;
    while(q--){
        cin>>s>>x>>y;
        if(s=="Add"){
            x--;
            g[x].push_back({par.size(),y});
            depth.push_back(depth[x]+1);
            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=sol=LCA(x,y,par,w,depth);
            best=sol;
            //cout<<sol<<'\n';
            dfs(y,g,0,sol);
            cout<<best<<'\n';
        }
    }
}

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:77:24: warning: operation on 'sol' may be undefined [-Wsequence-point]
   77 |             int sol=sol=LCA(x,y,par,w,depth);
      |                     ~~~^~~~~~~~~~~~~~~~~~~~~
klasika.cpp:48:15: warning: unused variable 'sz' [-Wunused-variable]
   48 |     int q,x,y,sz=1;
      |               ^~

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