oj.uz

Submission #943595

# Submission time Handle Problem Language Result Execution time Memory
943595 2024-03-11T16:06:18 Z Ahmed57 Prize (CEOI22_prize) C++17
54 / 100
 2229 ms 694420 KB 
#include "bits/stdc++.h"
 
using namespace std;
#define int long long
#ifdef LOCAL
#include "debug.cpp"
#else
#define debug(...)
#endif
int n;
int bit[2][600015];
void add(int e,int v,int ty){
    while(e<=n){
        bit[ty][e]+=v;
        e+=e&-e;
    }
}
int sum(int e,int ty){
    int su = 0;
    while(e>=1){
        su+=bit[ty][e];
        e-=e&-e;
    }
    return su;
}
int in[600001][2],outt[600001][2],timer = 0;
int P[600001][2][20];
int PR[600001][2][20],cost[600001][2][20];
int DEP[600001][2];
int dep[600001][2];
vector<int> adj[2][600001],vert[600001][2];
vector<pair<int,int>> lens[600001][2],computed[600001][2];
void dfs(int i,int pr,int ty){
    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 comp(int i,int pr,int ty){
    for(auto j:vert[i][ty]){
        comp(j,i,ty);
    }
    if(ty==0){
        sort(vert[i][ty].begin(),vert[i][ty].end(),comp1);
    }else{
        sort(vert[i][ty].begin(),vert[i][ty].end(),comp2);
    }
    vector<pair<int,int>> lol;
    for(auto j:lens[i][ty]){
        if(j.first!=i)lol.push_back({in[j.first][ty],j.second});
    }
    sort(lol.begin(),lol.end());
    int it = 0;
    for(auto j:vert[i][ty]){
        if(it==lol.size()){
            cout<<"a333"<<endl;
            exit(0);
        }
        while(lol[it].first<in[j][ty])it++;
        if(it==lol.size()){
            cout<<"a333"<<endl;
            exit(0);
        }
        int diff = lol[it].second-sum(lol[it].first,ty);
        computed[i][ty].push_back({j,diff});
        add(in[j][ty],diff,ty);
        add(outt[j][ty]+1,-diff,ty);
    }
}
void dfs2(int i,int pr,int dist,int ty){
    PR[i][ty][0] = pr;
    cost[i][ty][0] = dist;
    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:computed[i][ty]){
        if(j.first==pr)continue;
        dfs2(j.first,i,j.second,ty);
    }
}
int lca2(int a,int b,int ty){
    if(DEP[a][ty]<DEP[b][ty])swap(a,b);
    int 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};
}
vector<pair<int,int>> queries;
vector<int> v1,st1,v2,st2;set<int> loli,loli2;
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    //freopen("prize.in.1c","r",stdin);
    int k,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(int i = n-k+1;i<=n;i++){
        cout<<i<<" ";
    }
    cout<<endl;
    for(int i = n-k+1;i<=n;i++){
        v1.push_back(i);
        v2.push_back(i);
    }
    sort(v1.begin(),v1.end(),comp1);
    sort(v2.begin(),v2.end(),comp2);
    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++){
        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});
    }
    for(int i = 1;i<k;i++){
        int x,y,z,e;cin>>x>>y>>z>>e;
        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});
    }
    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;
    comp(st1[0],0,0);
    comp(st2[0],0,1);
    dfs2(st1[0],0,0,0);
    dfs2(st2[0],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 comp(long long int, long long int, long long int)':
Main.cpp:88:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         if(it==lol.size()){
      |            ~~^~~~~~~~~~~~
Main.cpp:93:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         if(it==lol.size()){
      |            ~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:210: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]
  210 |     for(int i = 1;i<v1.size();i++){
      |                   ~^~~~~~~~~~
Main.cpp:227: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]
  227 |     for(int i = 1;i<v2.size();i++){
      |                   ~^~~~~~~~~~
Main.cpp:168:8: warning: 'root1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  168 |     dfs(root1,0,0);
      |     ~~~^~~~~~~~~~~
Main.cpp:170:8: warning: 'root2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  170 |     dfs(root2,0,1);
      |     ~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1836 ms 435676 KB Output is correct
2 Correct 1978 ms 463060 KB Output is correct
3 Correct 1493 ms 606432 KB Output is correct
4 Correct 1452 ms 596008 KB Output is correct
5 Correct 1619 ms 630676 KB Output is correct
6 Correct 1955 ms 637012 KB Output is correct
7 Correct 1980 ms 639084 KB Output is correct
8 Correct 1918 ms 625268 KB Output is correct
9 Correct 1461 ms 597508 KB Output is correct
10 Correct 1642 ms 623220 KB Output is correct
11 Correct 1424 ms 578312 KB Output is correct
12 Correct 1569 ms 613928 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1924 ms 459700 KB Output is correct
2 Correct 1654 ms 420456 KB Output is correct
3 Correct 1532 ms 655484 KB Output is correct
4 Correct 1702 ms 678880 KB Output is correct
5 Correct 1572 ms 661888 KB Output is correct
6 Correct 1848 ms 654776 KB Output is correct
7 Correct 2229 ms 686856 KB Output is correct
8 Correct 2220 ms 688564 KB Output is correct
9 Correct 2024 ms 689224 KB Output is correct
10 Correct 2037 ms 694420 KB Output is correct
11 Correct 1796 ms 658264 KB Output is correct
12 Correct 2075 ms 691668 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1105 ms 364608 KB Output is correct
2 Correct 1124 ms 364260 KB Output is correct
3 Correct 853 ms 430732 KB Output is correct
4 Correct 825 ms 428684 KB Output is correct
5 Correct 818 ms 428864 KB Output is correct
6 Correct 986 ms 432780 KB Output is correct
7 Correct 976 ms 430748 KB Output is correct
8 Correct 986 ms 431540 KB Output is correct
9 Correct 914 ms 425896 KB Output is correct
10 Correct 862 ms 424384 KB Output is correct
11 Correct 866 ms 425732 KB Output is correct
12 Correct 920 ms 424680 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 895 ms 310748 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 901 ms 318944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -