oj.uz

Submission #943600

# Submission time Handle Problem Language Result Execution time Memory
943600 2024-03-11T16:11:31 Z Ahmed57 Prize (CEOI22_prize) C++17
76 / 100
 3496 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;
int bit[2][1000015];
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[1000001][2],outt[1000001][2],timer = 0;
int P[1000001][2][20];
int PR[1000001][2][20],cost[1000001][2][20];
int DEP[1000001][2];
int dep[1000001][2];
vector<int> adj[2][1000001],vert[1000001][2];
vector<pair<int,int>> lens[1000001][2],computed[1000001][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 1812 ms 502948 KB Output is correct
2 Correct 2093 ms 530132 KB Output is correct
3 Correct 1564 ms 665568 KB Output is correct
4 Correct 1498 ms 653036 KB Output is correct
5 Correct 1704 ms 694080 KB Output is correct
6 Correct 2047 ms 699812 KB Output is correct
7 Correct 1992 ms 700748 KB Output is correct
8 Correct 1963 ms 686228 KB Output is correct
9 Correct 1468 ms 660808 KB Output is correct
10 Correct 1630 ms 688196 KB Output is correct
11 Correct 1416 ms 641604 KB Output is correct
12 Correct 1587 ms 695764 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1977 ms 533176 KB Output is correct
2 Correct 1685 ms 495332 KB Output is correct
3 Correct 1666 ms 731980 KB Output is correct
4 Correct 1834 ms 754392 KB Output is correct
5 Correct 1651 ms 739168 KB Output is correct
6 Correct 1893 ms 730140 KB Output is correct
7 Correct 2163 ms 761468 KB Output is correct
8 Correct 2299 ms 761180 KB Output is correct
9 Correct 2073 ms 761436 KB Output is correct
10 Correct 2154 ms 766652 KB Output is correct
11 Correct 1843 ms 730612 KB Output is correct
12 Correct 2025 ms 768256 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1114 ms 440584 KB Output is correct
2 Correct 1053 ms 440952 KB Output is correct
3 Correct 860 ms 519888 KB Output is correct
4 Correct 861 ms 519512 KB Output is correct
5 Correct 799 ms 521532 KB Output is correct
6 Correct 1002 ms 533472 KB Output is correct
7 Correct 994 ms 533600 KB Output is correct
8 Correct 950 ms 528332 KB Output is correct
9 Correct 928 ms 532320 KB Output is correct
10 Correct 888 ms 529068 KB Output is correct
11 Correct 915 ms 532584 KB Output is correct
12 Correct 870 ms 522232 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2633 ms 673168 KB Output is correct
2 Correct 2584 ms 673508 KB Output is correct
3 Correct 1848 ms 654360 KB Output is correct
4 Correct 1761 ms 655276 KB Output is correct
5 Correct 1773 ms 656116 KB Output is correct
6 Correct 2229 ms 665032 KB Output is correct
7 Correct 2252 ms 665332 KB Output is correct
8 Correct 2318 ms 694592 KB Output is correct
9 Correct 2023 ms 664776 KB Output is correct
10 Correct 1978 ms 666280 KB Output is correct
11 Correct 2068 ms 665892 KB Output is correct
12 Correct 2099 ms 664156 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3496 ms 770176 KB Output is correct
2 Correct 3398 ms 764340 KB Output is correct
3 Runtime error 2242 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -