oj.uz

Submission #943862

# Submission time Handle Problem Language Result Execution time Memory
943862 2024-03-12T02:53:17 Z Ahmed57 Prize (CEOI22_prize) C++17
100 / 100
 2926 ms 625996 KB 
#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
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];
int cost[1300001][2][20];
int dep[1000001][2];
int root[1000001][2];
bool vis[1000001][2];
vector<int> adj[2][1000001],vert[1000001][2];
vector<pair<int,int>> 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,int 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){
    P[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++){
        P[i][ty][j] = P[P[i][ty][j-1]][ty][j-1];
        cost[i][ty][j] = cost[i][ty][j-1]+cost[P[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 = P[a][ty][i];
        }
    }
    if(a==b)return summ;
    for(int i = 19;i>=0;i--){
        if(P[a][ty][i]!=P[b][ty][i]){
            summ+=cost[a][ty][i];
            summ+=cost[b][ty][i];
            a = P[a][ty][i];
            b = P[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.flush();
    cout<<"!"<<endl;
    for(int i = 1;i<k;i++){
        int 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){
        cout<<lca2(i.first,i.second,0)<<" "<<lca2(i.first,i.second,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 1528 ms 397248 KB Output is correct
2 Correct 1502 ms 406272 KB Output is correct
3 Correct 1047 ms 374604 KB Output is correct
4 Correct 1079 ms 373228 KB Output is correct
5 Correct 1189 ms 379732 KB Output is correct
6 Correct 1394 ms 381508 KB Output is correct
7 Correct 1333 ms 381464 KB Output is correct
8 Correct 1368 ms 379952 KB Output is correct
9 Correct 1095 ms 374332 KB Output is correct
10 Correct 1138 ms 378100 KB Output is correct
11 Correct 1004 ms 371236 KB Output is correct
12 Correct 1101 ms 377036 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2056 ms 405252 KB Output is correct
2 Correct 1797 ms 393512 KB Output is correct
3 Correct 1313 ms 376324 KB Output is correct
4 Correct 1367 ms 380576 KB Output is correct
5 Correct 1280 ms 377528 KB Output is correct
6 Correct 1523 ms 377812 KB Output is correct
7 Correct 1664 ms 385044 KB Output is correct
8 Correct 1746 ms 386224 KB Output is correct
9 Correct 1645 ms 387880 KB Output is correct
10 Correct 1626 ms 387548 KB Output is correct
11 Correct 1320 ms 379792 KB Output is correct
12 Correct 1600 ms 386532 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 943 ms 378324 KB Output is correct
2 Correct 1018 ms 377788 KB Output is correct
3 Correct 708 ms 353236 KB Output is correct
4 Correct 705 ms 355560 KB Output is correct
5 Correct 726 ms 355896 KB Output is correct
6 Correct 821 ms 359156 KB Output is correct
7 Correct 769 ms 357284 KB Output is correct
8 Correct 720 ms 359384 KB Output is correct
9 Correct 727 ms 359772 KB Output is correct
10 Correct 727 ms 357644 KB Output is correct
11 Correct 817 ms 303064 KB Output is correct
12 Correct 785 ms 359512 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1926 ms 599508 KB Output is correct
2 Correct 1968 ms 599460 KB Output is correct
3 Correct 1555 ms 555372 KB Output is correct
4 Correct 1530 ms 553488 KB Output is correct
5 Correct 1538 ms 527276 KB Output is correct
6 Correct 1723 ms 410688 KB Output is correct
7 Correct 1707 ms 410348 KB Output is correct
8 Correct 1733 ms 561648 KB Output is correct
9 Correct 1612 ms 410692 KB Output is correct
10 Correct 1593 ms 562408 KB Output is correct
11 Correct 1576 ms 563376 KB Output is correct
12 Correct 1556 ms 563064 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2926 ms 625996 KB Output is correct
2 Correct 2793 ms 624240 KB Output is correct
3 Correct 1921 ms 573016 KB Output is correct
4 Correct 2076 ms 581940 KB Output is correct
5 Correct 1833 ms 570876 KB Output is correct
6 Correct 2725 ms 590628 KB Output is correct
7 Correct 2404 ms 579648 KB Output is correct
8 Correct 2569 ms 585856 KB Output is correct
9 Correct 2325 ms 584572 KB Output is correct
10 Correct 2305 ms 582292 KB Output is correct
11 Correct 2318 ms 582268 KB Output is correct
12 Correct 2419 ms 587764 KB Output is correct