oj.uz

Submission #943852

# Submission time Handle Problem Language Result Execution time Memory
943852 2024-03-12T02:37:19 Z Ahmed57 Prize (CEOI22_prize) C++17
76 / 100
 3500 ms 895020 KB 
#include "bits/stdc++.h"
 
using namespace std;
#ifdef LOCAL
#include "debug.cpp"
#else
#define debug(...)
#endif
int n,k;

vector<pair<int,int>> queries;
vector<int> v1,st1,v2,st2;set<int> loli,loli2;
int in[1300001][2],outt[1300001][2],timer = 0;
int P[1300001][2][20];
long long PR[1300001][2][20],cost[1300001][2][20];
int DEP[1300001][2];
long long dep[1300001][2];
int root[1300001][2],vis[1300001][2];
vector<int> adj[2][1300001],vert[1300001][2];
vector<pair<int,long long>> lens[1300001][2];
void dfs(int i,int pr,int ty){
    if(ty){
        if(v1.size()<k)v1.push_back(i);
        if(v2.size()<k)v2.push_back(i);
    }
    in[i][ty] = ++timer;
    P[i][ty][0] = pr;
    dep[i][ty] = dep[pr][ty]+1;
    for(int j = 1;j<20;j++){
        P[i][ty][j] = P[P[i][ty][j-1]][ty][j-1];
    }
    for(auto j:adj[ty][i]){
        if(j==pr)continue;
        dfs(j,i,ty);
    }
    outt[i][ty] = timer;
}
bool comp1(int a,int b){
    return in[a][0]<in[b][0];
}
bool comp2(int a,int b){
    return in[a][1]<in[b][1];
}
int lca(int a,int b,int ty){
    if(dep[a][ty]<dep[b][ty])swap(a,b);
    for(int i = 19;i>=0;i--){
        if(dep[a][ty]-(1<<i)>=dep[b][ty]){
            a = P[a][ty][i];
        }
    }
    if(a==b)return a;
    for(int i = 19;i>=0;i--){
        if(P[a][ty][i]!=P[b][ty][i]){
            a = P[a][ty][i];
            b = P[b][ty][i];
        }
    }
    return P[a][ty][0];
}
bool upper(int a,int b,int ty){
    return in[a][ty]<=in[b][ty]&&outt[a][ty]>=outt[b][ty];
}
void dfs3(int i,int pr,long long cost,int ty){
    root[i][ty] = cost;
    vis[i][ty] = 1;
    for(auto j:lens[i][ty]){
        if(!vis[j.first][ty]){
            dfs3(j.first,i,cost+j.second,ty);
        }
    }
}
void dfs2(int i,int pr,int ty){
    PR[i][ty][0] = pr;
    cost[i][ty][0] = root[i][ty]-root[pr][ty];
    DEP[i][ty] = DEP[pr][ty]+1;
    for(int j = 1;j<20;j++){
        PR[i][ty][j] = PR[PR[i][ty][j-1]][ty][j-1];
        cost[i][ty][j] = cost[i][ty][j-1]+cost[PR[i][ty][j-1]][ty][j-1];
    }
    for(auto j:vert[i][ty]){
        if(j==pr)continue;
        dfs2(j,i,ty);
    }
}
long long lca2(int a,int b,int ty){
    if(DEP[a][ty]<DEP[b][ty])swap(a,b);
    long long summ = 0;
    for(int i = 19;i>=0;i--){
        if(DEP[a][ty]-(1<<i)>=DEP[b][ty]){
            summ+=cost[a][ty][i];
            a = PR[a][ty][i];
        }
    }
    if(a==b)return summ;
    for(int i = 19;i>=0;i--){
        if(PR[a][ty][i]!=PR[b][ty][i]){
            summ+=cost[a][ty][i];
            summ+=cost[b][ty][i];
            a = PR[a][ty][i];
            b = PR[b][ty][i];
        }
    }
    return summ+cost[a][ty][0]+cost[b][ty][0];
}
void query(int a,int b){
    cout<<"? "<<a<<" "<<b<<endl;
    //int x,y,z,e;
    //cin>>x>>y>>z>>e;
    //return {x,y,z,e};
}
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    //freopen("prize.in.1c","r",stdin);
    int g,t;
    cin>>n>>k>>g>>t;
    int root1 , root2;
    for(int i = 1;i<=n;i++){
        int x;cin>>x;
        if(x==-1){
            root1 = i;
        }else{
            adj[0][x].push_back(i);
            adj[0][i].push_back(x);
        }
    }
    for(int i = 1;i<=n;i++){
        int x;cin>>x;
        if(x==-1){
            root2 = i;
        }else{
            adj[1][x].push_back(i);
            adj[1][i].push_back(x);
        }
    }
    dfs(root1,0,0);
    timer = 0;
    dfs(root2,0,1);
    for(auto i:v1){
        cout<<i<<" ";
    }
    cout<<endl;
    sort(v1.begin(),v1.end(),comp1);
    sort(v2.begin(),v2.end(),comp1);
    for(int i = 1;i<k;i++){
        query(v1[i-1],v1[i]);
        //lens[lca(v[i],v[i-1],0)].push_back({v[i-1],lol[0]});
        //lens[lca(v[i],v[i-1],0)].push_back({v[i],lol[1]});
        v1.push_back(lca(v1[i],v1[i-1],0));
    }
    for(int i = 1;i<k;i++){
        //query(v2[i-1],v2[i]);
        //lens[lca(v[i],v[i-1],0)].push_back({v[i-1],lol[0]});
        //lens[lca(v[i],v[i-1],0)].push_back({v[i],lol[1]});
        v2.push_back(lca(v2[i],v2[i-1],1));
    }
    cout<<"!"<<endl;
    for(int i = 1;i<k;i++){
        long long x,y,z,e;cin>>x>>y>>z>>e;
        lens[lca(v1[i],v1[i-1],0)][0].push_back({v1[i-1],x});
        lens[lca(v1[i],v1[i-1],0)][0].push_back({v1[i],y});
        lens[v1[i-1]][0].push_back({lca(v1[i],v1[i-1],0),-x});
        lens[v1[i]][0].push_back({lca(v1[i],v1[i-1],0),-y});
        lens[lca(v2[i],v2[i-1],1)][1].push_back({v2[i-1],z});
        lens[lca(v2[i],v2[i-1],1)][1].push_back({v2[i],e});
        lens[v2[i-1]][1].push_back({lca(v2[i],v2[i-1],1),-z});
        lens[v2[i]][1].push_back({lca(v2[i],v2[i-1],1),-e});
    }
    sort(v1.begin(),v1.end(),comp1);
    for(auto i:v1)loli.insert(i);
    v1.clear();
    for(auto i:loli)v1.push_back(i);
    sort(v1.begin(),v1.end(),comp1);
    st1.push_back(v1[0]);
    for(int i = 1;i<v1.size();i++){
        while(st1.size()>1&&!upper(st1.back(),v1[i],0)){
            vert[st1[st1.size()-2]][0].push_back(st1.back());
            st1.pop_back();
        }
        st1.push_back(v1[i]);
    }
    while(st1.size()>1){
        vert[st1[st1.size()-2]][0].push_back(st1.back());
        st1.pop_back();
    }
    sort(v2.begin(),v2.end(),comp2);
    for(auto i:v2)loli2.insert(i);
    v2.clear();
    for(auto i:loli2)v2.push_back(i);
    sort(v2.begin(),v2.end(),comp2);
    st2.push_back(v2[0]);
    for(int i = 1;i<v2.size();i++){
        while(st2.size()>1&&!upper(st2.back(),v2[i],1)){
            vert[st2[st2.size()-2]][1].push_back(st2.back());
            st2.pop_back();
        }
        st2.push_back(v2[i]);
    }
    while(st2.size()>1){
        vert[st2[st2.size()-2]][1].push_back(st2.back());
        st2.pop_back();
    }
    timer = 0;
    dfs3(st1[0],0,0,0);
    dfs3(st2[0],0,0,1);
    dfs2(st1[0],0,0);
    dfs2(st2[0],0,1);
    while(t--){
        int a,b;cin>>a>>b;
        queries.push_back({a,b});
    }
    for(auto i:queries){
        int a = i.first , b = i.second;
        cout<<lca2(a,b,0)<<" "<<lca2(a,b,1)<<endl;
    }
}

Compilation message

Main.cpp: In function 'void dfs(int, int, int)':
Main.cpp:23:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |         if(v1.size()<k)v1.push_back(i);
      |            ~~~~~~~~~^~
Main.cpp:24:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |         if(v2.size()<k)v2.push_back(i);
      |            ~~~~~~~~~^~
Main.cpp: In function 'int main()':
Main.cpp:174:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |     for(int i = 1;i<v1.size();i++){
      |                   ~^~~~~~~~~~
Main.cpp:191:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |     for(int i = 1;i<v2.size();i++){
      |                   ~^~~~~~~~~~
Main.cpp:135:8: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  135 |     dfs(root1,0,0);
      |     ~~~^~~~~~~~~~~
Main.cpp:137:8: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  137 |     dfs(root2,0,1);
      |     ~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1811 ms 665784 KB Output is correct
2 Correct 1927 ms 694188 KB Output is correct
3 Correct 1272 ms 635932 KB Output is correct
4 Correct 1252 ms 631072 KB Output is correct
5 Correct 1397 ms 655300 KB Output is correct
6 Correct 1696 ms 652224 KB Output is correct
7 Correct 1720 ms 651812 KB Output is correct
8 Correct 1674 ms 645120 KB Output is correct
9 Correct 1282 ms 634756 KB Output is correct
10 Correct 1385 ms 651816 KB Output is correct
11 Correct 1229 ms 619848 KB Output is correct
12 Correct 1335 ms 647576 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2164 ms 688912 KB Output is correct
2 Correct 1814 ms 642076 KB Output is correct
3 Correct 1569 ms 655488 KB Output is correct
4 Correct 1717 ms 667676 KB Output is correct
5 Correct 1599 ms 657684 KB Output is correct
6 Correct 2340 ms 632680 KB Output is correct
7 Correct 2485 ms 661536 KB Output is correct
8 Correct 2356 ms 667536 KB Output is correct
9 Correct 2129 ms 669564 KB Output is correct
10 Correct 2213 ms 674684 KB Output is correct
11 Correct 1891 ms 647356 KB Output is correct
12 Correct 2154 ms 675428 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1211 ms 349992 KB Output is correct
2 Correct 1464 ms 347176 KB Output is correct
3 Correct 843 ms 318756 KB Output is correct
4 Correct 910 ms 318656 KB Output is correct
5 Correct 932 ms 326268 KB Output is correct
6 Correct 1306 ms 497388 KB Output is correct
7 Correct 1169 ms 327796 KB Output is correct
8 Correct 1039 ms 323808 KB Output is correct
9 Correct 1123 ms 405460 KB Output is correct
10 Correct 1113 ms 329004 KB Output is correct
11 Correct 1041 ms 323872 KB Output is correct
12 Correct 1064 ms 324152 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3036 ms 518468 KB Output is correct
2 Correct 3462 ms 543640 KB Output is correct
3 Correct 2054 ms 469740 KB Output is correct
4 Correct 1975 ms 466984 KB Output is correct
5 Correct 1958 ms 466912 KB Output is correct
6 Correct 2492 ms 478836 KB Output is correct
7 Correct 2591 ms 481036 KB Output is correct
8 Correct 2569 ms 478292 KB Output is correct
9 Correct 2253 ms 477580 KB Output is correct
10 Correct 2297 ms 479240 KB Output is correct
11 Correct 2281 ms 479508 KB Output is correct
12 Correct 2174 ms 477300 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3644 ms 895020 KB Time limit exceeded
2 Halted 0 ms 0 KB -