oj.uz

Submission #637924

# Submission time Handle Problem Language Result Execution time Memory
637924 2022-09-03T15:26:15 Z Iwanttobreakfree Klasika (COCI20_klasika) C++17
33 / 110
 152 ms 2980 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 372 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 372 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 6 ms 468 KB Output is correct
14 Correct 5 ms 596 KB Output is correct
15 Correct 5 ms 724 KB Output is correct
16 Correct 5 ms 892 KB Output is correct
17 Correct 4 ms 468 KB Output is correct
18 Correct 4 ms 596 KB Output is correct
19 Correct 4 ms 724 KB Output is correct
20 Correct 4 ms 724 KB Output is correct
21 Correct 5 ms 468 KB Output is correct
22 Correct 5 ms 640 KB Output is correct
23 Correct 4 ms 760 KB Output is correct
24 Correct 4 ms 768 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 152 ms 2980 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 372 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 6 ms 468 KB Output is correct
14 Correct 5 ms 596 KB Output is correct
15 Correct 5 ms 724 KB Output is correct
16 Correct 5 ms 892 KB Output is correct
17 Correct 4 ms 468 KB Output is correct
18 Correct 4 ms 596 KB Output is correct
19 Correct 4 ms 724 KB Output is correct
20 Correct 4 ms 724 KB Output is correct
21 Correct 5 ms 468 KB Output is correct
22 Correct 5 ms 640 KB Output is correct
23 Correct 4 ms 760 KB Output is correct
24 Correct 4 ms 768 KB Output is correct
25 Runtime error 152 ms 2980 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -