oj.uz

Submission #943855

# Submission time Handle Problem Language Result Execution time Memory
943855 2024-03-12T02:43:55 Z Ahmed57 Prize (CEOI22_prize) C++17
76 / 100
 2779 ms 1048576 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[1000001][2],outt[1000001][2],timer = 0;
int P[1000001][2][20];
long long PR[1000001][2][20],cost[1300001][2][20];
int DEP[1000001][2];
long long dep[1000001][2];
int root[1000001][2],vis[1000001][2];
vector<int> adj[2][1000001],vert[1000001][2];
vector<pair<int,long long>> lens[1000001][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<<"\n";
    //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;
    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)<<"\n";
    }
    cout<<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:175:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |     for(int i = 1;i<v1.size();i++){
      |                   ~^~~~~~~~~~
Main.cpp:192:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |     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 1672 ms 656740 KB Output is correct
2 Correct 1751 ms 666672 KB Output is correct
3 Correct 1154 ms 624848 KB Output is correct
4 Correct 1206 ms 623728 KB Output is correct
5 Correct 1273 ms 631556 KB Output is correct
6 Correct 1546 ms 633924 KB Output is correct
7 Correct 1575 ms 634064 KB Output is correct
8 Correct 1562 ms 632848 KB Output is correct
9 Correct 1152 ms 624596 KB Output is correct
10 Correct 1407 ms 629488 KB Output is correct
11 Correct 1224 ms 621136 KB Output is correct
12 Correct 1265 ms 629348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2044 ms 664892 KB Output is correct
2 Correct 1721 ms 651572 KB Output is correct
3 Correct 1439 ms 627352 KB Output is correct
4 Correct 1483 ms 634624 KB Output is correct
5 Correct 1351 ms 628460 KB Output is correct
6 Correct 1651 ms 629020 KB Output is correct
7 Correct 1897 ms 638436 KB Output is correct
8 Correct 1909 ms 639148 KB Output is correct
9 Correct 1707 ms 642940 KB Output is correct
10 Correct 1838 ms 643068 KB Output is correct
11 Correct 1530 ms 632744 KB Output is correct
12 Correct 1817 ms 643304 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1049 ms 603468 KB Output is correct
2 Correct 1039 ms 600964 KB Output is correct
3 Correct 770 ms 593164 KB Output is correct
4 Correct 787 ms 597108 KB Output is correct
5 Correct 784 ms 591544 KB Output is correct
6 Correct 935 ms 605148 KB Output is correct
7 Correct 875 ms 604360 KB Output is correct
8 Correct 993 ms 598168 KB Output is correct
9 Correct 819 ms 598760 KB Output is correct
10 Correct 932 ms 596428 KB Output is correct
11 Correct 900 ms 600740 KB Output is correct
12 Correct 856 ms 603724 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2509 ms 897584 KB Output is correct
2 Correct 2306 ms 902248 KB Output is correct
3 Correct 1707 ms 846224 KB Output is correct
4 Correct 1740 ms 843932 KB Output is correct
5 Correct 1755 ms 841576 KB Output is correct
6 Correct 2198 ms 854216 KB Output is correct
7 Correct 2085 ms 851152 KB Output is correct
8 Correct 2139 ms 855744 KB Output is correct
9 Correct 1900 ms 854584 KB Output is correct
10 Correct 1889 ms 855852 KB Output is correct
11 Correct 1869 ms 855764 KB Output is correct
12 Correct 1970 ms 854832 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2779 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -