Submission #943610

#	Time	Username	Problem	Language	Result	Execution time	Memory
943610		Ahmed57	Prize (CEOI22_prize)	C++17	76 / 100	3548 ms	828072 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 0 / 24