oj.uz

Submission #637943

# Submission time Handle Problem Language Result Execution time Memory
637943 2022-09-03T16:26:40 Z Iwanttobreakfree Klasika (COCI20_klasika) C++17
33 / 110
 53 ms 13300 KB 
#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=17;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=17;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=17;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>(18));
    vector<vector<int>> w(1,vector<int>(18));
    vector<int> depth(1),root1(1);
    for(int i=0;i<18;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(18),wx(18);
            wx[0]=y;
            parx[0]=x;
            for(int i=1;i<18;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

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

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 8 ms 1552 KB Output is correct
14 Correct 9 ms 2832 KB Output is correct
15 Correct 10 ms 3080 KB Output is correct
16 Correct 12 ms 5424 KB Output is correct
17 Correct 5 ms 1552 KB Output is correct
18 Correct 9 ms 2904 KB Output is correct
19 Correct 7 ms 3080 KB Output is correct
20 Correct 7 ms 3720 KB Output is correct
21 Correct 6 ms 1552 KB Output is correct
22 Correct 8 ms 2828 KB Output is correct
23 Correct 8 ms 3080 KB Output is correct
24 Correct 8 ms 3720 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 13300 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 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 8 ms 1552 KB Output is correct
14 Correct 9 ms 2832 KB Output is correct
15 Correct 10 ms 3080 KB Output is correct
16 Correct 12 ms 5424 KB Output is correct
17 Correct 5 ms 1552 KB Output is correct
18 Correct 9 ms 2904 KB Output is correct
19 Correct 7 ms 3080 KB Output is correct
20 Correct 7 ms 3720 KB Output is correct
21 Correct 6 ms 1552 KB Output is correct
22 Correct 8 ms 2828 KB Output is correct
23 Correct 8 ms 3080 KB Output is correct
24 Correct 8 ms 3720 KB Output is correct
25 Runtime error 53 ms 13300 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -