Submission #579062

#	Time	Username	Problem	Language	Result	Execution time	Memory
579062		ogibogi2004	Highway Tolls (IOI18_highway)	C++14	100 / 100	264 ms	12328 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=9e4+6;
const int MAXM=(1<<17);
vector<pair<int,int> >g[MAXN];
int distu[MAXN],distv[MAXN];
int parEdgeU[MAXN];
int parEdgeV[MAXN];
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size();
    for(int i=0;i<M;i++)
    {
        g[U[i]].push_back({V[i],i});
        g[V[i]].push_back({U[i],i});
    }
    vector<int>w;
    w=vector<int>(M,0);
    long long dist=(long long)ask(w);
    long long low=0,high=M-1,best;
    while(low<=high)
    {
        int mid=(low+high)/2;
        for(int j=0;j<w.size();j++)w[j]=0;
        for(int j=0;j<=mid;j++)
        {
            w[j]=1;
        }
        if(ask(w)==dist)
        {
            low=mid+1;
        }
        else
        {
            best=mid;
            high=mid-1;
        }
    }
    int u=U[best],v=V[best];
    queue<int>bfsu,bfsv;
    bfsu.push(u);
    bfsv.push(v);
    memset(distu,-1,sizeof(distu));
    memset(distv,-1,sizeof(distv));
    distu[u]=0;
    parEdgeU[u]=-1;
    distv[v]=0;
    parEdgeV[v]=-1;
    vector<pair<int,int> >tv,tu;
    while(!bfsu.empty())
    {
        int t=bfsu.front();
        bfsu.pop();
        for(auto xd:g[t])
        {
            if(distu[xd.first]==-1)
            {
                distu[xd.first]=distu[t]+1;
                parEdgeU[xd.first]=xd.second;
                bfsu.push(xd.first);
            }
        }
    }
    while(!bfsv.empty())
    {
        int t=bfsv.front();
        bfsv.pop();
        for(auto xd:g[t])
        {
            if(distv[xd.first]==-1)
            {
                distv[xd.first]=distv[t]+1;
                parEdgeV[xd.first]=xd.second;
                bfsv.push(xd.first);
            }
        }
    }
    for(int i=0;i<N;i++)
    {
        if(distu[i]<distv[i])
        {
            tu.push_back({distu[i],i});
        }
        else
        {
            tv.push_back({distv[i],i});
        }
    }
    sort(tu.begin(),tu.end());
    sort(tv.begin(),tv.end());
    low=0,high=tu.size()-1;
    int s,t;
    while(low<=high)
    {
        int mid=(low+high)/2;
        for(int j=0;j<w.size();j++)w[j]=0;
        w[best]=1;
        for(int j=1;j<=mid;j++)
        {
            w[parEdgeU[tu[j].second]]=1;
        }
        for(int j=1;j<tv.size();j++)
        {
            w[parEdgeV[tv[j].second]]=1;
        }
        for(int j=0;j<w.size();j++)w[j]=1-w[j];
        /*for(int j=0;j<w.size();j++)cout<<w[j]<<" ";
        cout<<endl;
        cout<<low<<" "<<high<<" "<<mid<<" "<<ask(w)<<endl;*/
        if(ask(w)>(long long)dist)
        {
            low=mid+1;
        }
        else
        {
            s=tu[mid].second;
            high=mid-1;
        }
    }
    low=0;high=tv.size()-1;
    //cout<<"dist: "<<dist<<" "<<dist*1ll/A*1ll*B<<endl;
    while(low<=high)
    {
        int mid=(low+high)/2;
        for(int j=0;j<w.size();j++)w[j]=0;
        w[best]=1;
        for(int j=1;j<=mid;j++)
        {
            w[parEdgeV[tv[j].second]]=1;
        }
        for(int j=1;j<tu.size();j++)
        {
            w[parEdgeU[tu[j].second]]=1;
        }
        for(int j=0;j<w.size();j++)w[j]=1-w[j];
        /*for(int j=0;j<w.size();j++)cout<<w[j]<<" ";
        cout<<endl;
        cout<<low<<" "<<high<<" "<<mid<<" "<<ask(w)<<endl;*/
        if(ask(w)>(long long)dist)
        {
            low=mid+1;
        }
        else
        {
            t=tv[mid].second;
            high=mid-1;
        }
    }
    /*cout<<"tu:\n";
    for(auto xd:tu)cout<<xd.second<<" ";
    cout<<endl;

    cout<<"tv:\n";
    for(auto xd:tv)cout<<xd.second<<" ";
    cout<<endl;
    cout<<s<<" "<<t<<endl;
    cout<<s<<" "<<t<<endl;*/
    answer(s,t);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int j=0;j<w.size();j++)w[j]=0;
      |                     ~^~~~~~~~~
highway.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(int j=0;j<w.size();j++)w[j]=0;
      |                     ~^~~~~~~~~
highway.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(int j=1;j<tv.size();j++)
      |                     ~^~~~~~~~~~
highway.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int j=0;j<w.size();j++)w[j]=1-w[j];
      |                     ~^~~~~~~~~
highway.cpp:125:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for(int j=0;j<w.size();j++)w[j]=0;
      |                     ~^~~~~~~~~
highway.cpp:131:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         for(int j=1;j<tu.size();j++)
      |                     ~^~~~~~~~~~
highway.cpp:135:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |         for(int j=0;j<w.size();j++)w[j]=1-w[j];
      |                     ~^~~~~~~~~
highway.cpp:158:11: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  158 |     answer(s,t);
      |     ~~~~~~^~~~~
highway.cpp:158:11: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:39:17: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |     int u=U[best],v=V[best];
      |                 ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 31 / 31