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 <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=200005;
vector<int> v[nmax];
int d[4][nmax];
int q[nmax];
int p,u,i,j,s,t,a,b,n,m,x,y,det_s,det_t,ans;
void bfs(int x,int wh)
{
q[u=1]=x;d[wh][x]=1;
for(p=1;p<=u;p++)
{
x=q[p];
for(i=0;i<v[x].size();i++)
if(!d[wh][v[x][i]])
{
d[wh][v[x][i]]=d[wh][x]+1;
q[++u]=v[x][i];
}
}
}
int main()
{
//freopen("data.in","r",stdin);
cin>>n>>m;
cin>>s>>t>>a>>b;
for(i=1;i<=m;i++)
{
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
bfs(s,0);
bfs(t,1);
bfs(a,2);
bfs(b,3);
det_s=0;det_t=0;
for(i=1;i<=n;i++)
{
if(d[0][i]+d[2][i]-1==d[0][a]&&d[0][i]+d[3][i]-1==d[0][b])
det_s=max(det_s,d[0][i]);
if(d[1][i]+d[2][i]-1==d[1][a]&&d[1][i]+d[3][i]-1==d[1][b])
det_t=max(det_t,d[1][i]);
}
// cout<<det_s<<' '<<det_t<<"p\n";
//cout<<d[0][a]<<' '<<d[1][a]<<'\n';
//cout<<d[0][b]<<' '<<d[1][b]<<'\n';
ans=min(d[1][a]-d[0][a]-(d[0][a]==d[0][b]),d[1][b]-d[0][b]-(d[0][b]==d[0][a]));
if(ans<0) ans=-1;
cout<<ans;
return 0;
}
Compilation message (stderr)
007.cpp: In function 'void bfs(int, int)':
007.cpp:16:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |