Submission #105823

#	Time	Username	Problem	Language	Result	Execution time	Memory
105823		Bodo171	007 (CEOI14_007)	C++14	100 / 100	677 ms	18324 KiB

007

#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=n+1;det_t=n+1;
    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=min(det_s,d[2][i]);
        if(d[1][i]+d[2][i]-1==d[1][a]&&d[1][i]+d[3][i]-1==d[1][b])
            det_t=min(det_t,d[2][i]);
    }
    int eq=(d[0][a]==d[0][b]&&det_s>det_t&&d[1][a]==d[1][b]);
    ans=min(d[1][a]-d[0][a]-eq,d[1][b]-d[0][b]-eq);
    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++)
                 ~^~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70