oj.uz

Submission #943861

# Submission time Handle Problem Language Result Execution time Memory
943861 2024-03-12T02:52:49 Z Ahmed57 Prize (CEOI22_prize) C++17
76 / 100
 3500 ms 641700 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];
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 1552 ms 405088 KB Output is correct
2 Correct 1660 ms 414324 KB Output is correct
3 Correct 1146 ms 374428 KB Output is correct
4 Correct 1105 ms 373668 KB Output is correct
5 Correct 1203 ms 379576 KB Output is correct
6 Correct 1474 ms 383080 KB Output is correct
7 Correct 1501 ms 383188 KB Output is correct
8 Correct 1428 ms 381172 KB Output is correct
9 Correct 1076 ms 374564 KB Output is correct
10 Correct 1194 ms 377988 KB Output is correct
11 Correct 1061 ms 370980 KB Output is correct
12 Correct 1232 ms 376816 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2106 ms 413144 KB Output is correct
2 Correct 1692 ms 401708 KB Output is correct
3 Correct 1308 ms 376272 KB Output is correct
4 Correct 1395 ms 380664 KB Output is correct
5 Correct 1306 ms 377736 KB Output is correct
6 Correct 1645 ms 379392 KB Output is correct
7 Correct 2070 ms 386740 KB Output is correct
8 Correct 1891 ms 387812 KB Output is correct
9 Correct 1800 ms 388876 KB Output is correct
10 Correct 1911 ms 389128 KB Output is correct
11 Correct 1667 ms 380628 KB Output is correct
12 Correct 2023 ms 389688 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1235 ms 386204 KB Output is correct
2 Correct 1218 ms 385792 KB Output is correct
3 Correct 839 ms 353744 KB Output is correct
4 Correct 816 ms 355916 KB Output is correct
5 Correct 828 ms 355648 KB Output is correct
6 Correct 975 ms 360520 KB Output is correct
7 Correct 985 ms 359064 KB Output is correct
8 Correct 931 ms 360808 KB Output is correct
9 Correct 891 ms 360668 KB Output is correct
10 Correct 913 ms 358948 KB Output is correct
11 Correct 955 ms 360748 KB Output is correct
12 Correct 925 ms 360652 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2500 ms 615604 KB Output is correct
2 Correct 2342 ms 615516 KB Output is correct
3 Correct 1781 ms 554320 KB Output is correct
4 Correct 1730 ms 555360 KB Output is correct
5 Correct 1679 ms 555036 KB Output is correct
6 Correct 2085 ms 564948 KB Output is correct
7 Correct 2104 ms 564432 KB Output is correct
8 Correct 2189 ms 564572 KB Output is correct
9 Correct 1878 ms 566064 KB Output is correct
10 Correct 1953 ms 565444 KB Output is correct
11 Correct 1984 ms 413556 KB Output is correct
12 Correct 1909 ms 413876 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3402 ms 641700 KB Output is correct
2 Execution timed out 3561 ms 639976 KB Time limit exceeded
3 Halted 0 ms 0 KB -