oj.uz

Submission #943857

# Submission time Handle Problem Language Result Execution time Memory
943857 2024-03-12T02:48:32 Z Ahmed57 Prize (CEOI22_prize) C++17
76 / 100
 3500 ms 811592 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 cost[1300001][2][20];
long long dep[1000001][2];
int root[1000001][2];
bool 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){
    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++){
        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 1593 ms 492104 KB Output is correct
2 Correct 1763 ms 502496 KB Output is correct
3 Correct 1171 ms 461764 KB Output is correct
4 Correct 1171 ms 460600 KB Output is correct
5 Correct 1305 ms 468116 KB Output is correct
6 Correct 1559 ms 471084 KB Output is correct
7 Correct 1479 ms 471112 KB Output is correct
8 Correct 1442 ms 468756 KB Output is correct
9 Correct 1153 ms 461672 KB Output is correct
10 Correct 1188 ms 466780 KB Output is correct
11 Correct 1058 ms 457468 KB Output is correct
12 Correct 1177 ms 465284 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1923 ms 502144 KB Output is correct
2 Correct 1587 ms 487788 KB Output is correct
3 Correct 1330 ms 464548 KB Output is correct
4 Correct 1449 ms 470508 KB Output is correct
5 Correct 1314 ms 465356 KB Output is correct
6 Correct 1590 ms 465516 KB Output is correct
7 Correct 1788 ms 475424 KB Output is correct
8 Correct 1824 ms 476004 KB Output is correct
9 Correct 1730 ms 477748 KB Output is correct
10 Correct 1843 ms 478504 KB Output is correct
11 Correct 1599 ms 468048 KB Output is correct
12 Correct 1797 ms 478948 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1140 ms 451656 KB Output is correct
2 Correct 1082 ms 459820 KB Output is correct
3 Correct 812 ms 435336 KB Output is correct
4 Correct 778 ms 437660 KB Output is correct
5 Correct 754 ms 435324 KB Output is correct
6 Correct 903 ms 444552 KB Output is correct
7 Correct 916 ms 443264 KB Output is correct
8 Correct 887 ms 444860 KB Output is correct
9 Correct 844 ms 442968 KB Output is correct
10 Correct 810 ms 443400 KB Output is correct
11 Correct 845 ms 445112 KB Output is correct
12 Correct 796 ms 443284 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2321 ms 779752 KB Output is correct
2 Correct 2310 ms 779780 KB Output is correct
3 Correct 1721 ms 719340 KB Output is correct
4 Correct 1756 ms 719476 KB Output is correct
5 Correct 1646 ms 719704 KB Output is correct
6 Correct 2040 ms 729084 KB Output is correct
7 Correct 2035 ms 729076 KB Output is correct
8 Correct 2040 ms 728488 KB Output is correct
9 Correct 2011 ms 729400 KB Output is correct
10 Correct 1959 ms 729132 KB Output is correct
11 Correct 1999 ms 730004 KB Output is correct
12 Correct 1974 ms 730268 KB Output is correct

Subtask #5
0 / 24.0

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