oj.uz

Submission #943854

# Submission time Handle Problem Language Result Execution time Memory
943854 2024-03-12T02:38:35 Z Ahmed57 Prize (CEOI22_prize) C++17
76 / 100
 2870 ms 1048576 KB 
#include "bits/stdc++.h"
 
using namespace std;
#define int long long
#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<<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(long long int, long long int, long long int)':
Main.cpp:24:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   24 |         if(v1.size()<k)v1.push_back(i);
      |            ~~~~~~~~~^~
Main.cpp:25:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   25 |         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: 'long long int' and 'std::vector<long long 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: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |     for(int i = 1;i<v2.size();i++){
      |                   ~^~~~~~~~~~
Main.cpp:136:8: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  136 |     dfs(root1,0,0);
      |     ~~~^~~~~~~~~~~
Main.cpp:138:8: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  138 |     dfs(root2,0,1);
      |     ~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2310 ms 713308 KB Output is correct
2 Correct 2163 ms 740888 KB Output is correct
3 Correct 1533 ms 684444 KB Output is correct
4 Correct 1601 ms 671124 KB Output is correct
5 Correct 1791 ms 704908 KB Output is correct
6 Correct 2110 ms 697432 KB Output is correct
7 Correct 2176 ms 698860 KB Output is correct
8 Correct 2142 ms 688020 KB Output is correct
9 Correct 1575 ms 683692 KB Output is correct
10 Correct 1706 ms 699708 KB Output is correct
11 Correct 1402 ms 656000 KB Output is correct
12 Correct 1674 ms 697164 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2870 ms 742200 KB Output is correct
2 Correct 2441 ms 688824 KB Output is correct
3 Correct 1765 ms 714056 KB Output is correct
4 Correct 1948 ms 723280 KB Output is correct
5 Correct 1877 ms 711676 KB Output is correct
6 Correct 2331 ms 694368 KB Output is correct
7 Correct 2539 ms 724972 KB Output is correct
8 Correct 2705 ms 726920 KB Output is correct
9 Correct 2329 ms 729148 KB Output is correct
10 Correct 2373 ms 739272 KB Output is correct
11 Correct 2206 ms 703200 KB Output is correct
12 Correct 2323 ms 745668 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1568 ms 394276 KB Output is correct
2 Correct 1229 ms 447824 KB Output is correct
3 Correct 827 ms 368508 KB Output is correct
4 Correct 927 ms 432332 KB Output is correct
5 Correct 844 ms 370576 KB Output is correct
6 Correct 1041 ms 592536 KB Output is correct
7 Correct 1121 ms 376944 KB Output is correct
8 Correct 1014 ms 430436 KB Output is correct
9 Correct 1046 ms 374256 KB Output is correct
10 Correct 900 ms 433368 KB Output is correct
11 Correct 1022 ms 375660 KB Output is correct
12 Correct 995 ms 459492 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2820 ms 765664 KB Output is correct
2 Correct 2836 ms 651364 KB Output is correct
3 Correct 2012 ms 611116 KB Output is correct
4 Correct 1887 ms 610492 KB Output is correct
5 Correct 1920 ms 611164 KB Output is correct
6 Correct 2700 ms 1046504 KB Output is correct
7 Correct 2338 ms 676672 KB Output is correct
8 Correct 2372 ms 679680 KB Output is correct
9 Correct 2187 ms 676996 KB Output is correct
10 Correct 2146 ms 676536 KB Output is correct
11 Correct 2168 ms 675064 KB Output is correct
12 Correct 2208 ms 840028 KB Output is correct

Subtask #5
0 / 24.0

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