oj.uz

Submission #943610

# Submission time Handle Problem Language Result Execution time Memory
943610 2024-03-11T16:22:19 Z Ahmed57 Prize (CEOI22_prize) C++17
76 / 100
 3500 ms 828072 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][1300015];
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[1300001][2],outt[1300001][2],timer = 0;
int P[1300001][2][20];
int PR[1300001][2][20],cost[1300001][2][20];
int DEP[1300001][2];
int dep[1300001][2];
vector<int> adj[2][1300001],vert[1300001][2];
vector<pair<int,int>> lens[1300001][2],computed[1300001][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 1792 ms 563884 KB Output is correct
2 Correct 1960 ms 593864 KB Output is correct
3 Correct 1581 ms 743304 KB Output is correct
4 Correct 1502 ms 736604 KB Output is correct
5 Correct 1686 ms 767576 KB Output is correct
6 Correct 2029 ms 772084 KB Output is correct
7 Correct 2035 ms 773860 KB Output is correct
8 Correct 2003 ms 760808 KB Output is correct
9 Correct 1512 ms 735268 KB Output is correct
10 Correct 1635 ms 757684 KB Output is correct
11 Correct 1436 ms 717868 KB Output is correct
12 Correct 1591 ms 752184 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2045 ms 592312 KB Output is correct
2 Correct 1766 ms 550924 KB Output is correct
3 Correct 1636 ms 790160 KB Output is correct
4 Correct 1741 ms 810540 KB Output is correct
5 Correct 1631 ms 792712 KB Output is correct
6 Correct 1926 ms 785636 KB Output is correct
7 Correct 2198 ms 817752 KB Output is correct
8 Correct 2178 ms 820012 KB Output is correct
9 Correct 2096 ms 820920 KB Output is correct
10 Correct 2437 ms 824712 KB Output is correct
11 Correct 1899 ms 792984 KB Output is correct
12 Correct 2076 ms 823008 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1112 ms 494568 KB Output is correct
2 Correct 1117 ms 494680 KB Output is correct
3 Correct 860 ms 582704 KB Output is correct
4 Correct 866 ms 584792 KB Output is correct
5 Correct 921 ms 584616 KB Output is correct
6 Correct 1131 ms 593184 KB Output is correct
7 Correct 1039 ms 592888 KB Output is correct
8 Correct 977 ms 583764 KB Output is correct
9 Correct 1020 ms 586232 KB Output is correct
10 Correct 998 ms 590696 KB Output is correct
11 Correct 1024 ms 586168 KB Output is correct
12 Correct 927 ms 587852 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2732 ms 733120 KB Output is correct
2 Correct 2794 ms 732888 KB Output is correct
3 Correct 1988 ms 716380 KB Output is correct
4 Correct 1965 ms 717644 KB Output is correct
5 Correct 1918 ms 717084 KB Output is correct
6 Correct 2373 ms 727384 KB Output is correct
7 Correct 2331 ms 727884 KB Output is correct
8 Correct 2278 ms 727872 KB Output is correct
9 Correct 2086 ms 726856 KB Output is correct
10 Correct 2154 ms 726816 KB Output is correct
11 Correct 2184 ms 726896 KB Output is correct
12 Correct 2247 ms 770632 KB Output is correct

Subtask #5
0 / 24.0

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