This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |