| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 105823 |
2019-04-15T08:12:37 Z |
Bodo171 |
007 (CEOI14_007) |
C++14 |
|
677 ms |
18324 KB |
#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
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 |
| 1 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 4 |
Correct |
8 ms |
4992 KB |
Output is correct |
| 5 |
Correct |
7 ms |
4992 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 7 |
Correct |
8 ms |
4992 KB |
Output is correct |
| 8 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 9 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 10 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 11 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 12 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 13 |
Correct |
8 ms |
4992 KB |
Output is correct |
| 14 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 15 |
Correct |
7 ms |
4992 KB |
Output is correct |
| 16 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 17 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 18 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 19 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 20 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 21 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 22 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 23 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 24 |
Correct |
9 ms |
5120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
7180 KB |
Output is correct |
| 2 |
Correct |
107 ms |
8056 KB |
Output is correct |
| 3 |
Correct |
81 ms |
7288 KB |
Output is correct |
| 4 |
Correct |
80 ms |
8176 KB |
Output is correct |
| 5 |
Correct |
53 ms |
7160 KB |
Output is correct |
| 6 |
Correct |
75 ms |
7288 KB |
Output is correct |
| 7 |
Correct |
56 ms |
7672 KB |
Output is correct |
| 8 |
Correct |
59 ms |
7544 KB |
Output is correct |
| 9 |
Correct |
86 ms |
7928 KB |
Output is correct |
| 10 |
Correct |
373 ms |
12416 KB |
Output is correct |
| 11 |
Correct |
132 ms |
9720 KB |
Output is correct |
| 12 |
Correct |
194 ms |
10872 KB |
Output is correct |
| 13 |
Correct |
144 ms |
10104 KB |
Output is correct |
| 14 |
Correct |
102 ms |
9208 KB |
Output is correct |
| 15 |
Correct |
158 ms |
11000 KB |
Output is correct |
| 16 |
Correct |
162 ms |
11228 KB |
Output is correct |
| 17 |
Correct |
140 ms |
10564 KB |
Output is correct |
| 18 |
Correct |
172 ms |
10616 KB |
Output is correct |
| 19 |
Correct |
288 ms |
11768 KB |
Output is correct |
| 20 |
Correct |
509 ms |
14712 KB |
Output is correct |
| 21 |
Correct |
255 ms |
13304 KB |
Output is correct |
| 22 |
Correct |
201 ms |
12148 KB |
Output is correct |
| 23 |
Correct |
212 ms |
13176 KB |
Output is correct |
| 24 |
Correct |
208 ms |
13048 KB |
Output is correct |
| 25 |
Correct |
212 ms |
12640 KB |
Output is correct |
| 26 |
Correct |
207 ms |
12140 KB |
Output is correct |
| 27 |
Correct |
201 ms |
13172 KB |
Output is correct |
| 28 |
Correct |
249 ms |
13280 KB |
Output is correct |
| 29 |
Correct |
355 ms |
13616 KB |
Output is correct |
| 30 |
Correct |
468 ms |
15480 KB |
Output is correct |
| 31 |
Correct |
282 ms |
14516 KB |
Output is correct |
| 32 |
Correct |
243 ms |
13308 KB |
Output is correct |
| 33 |
Correct |
225 ms |
13564 KB |
Output is correct |
| 34 |
Correct |
269 ms |
13708 KB |
Output is correct |
| 35 |
Correct |
338 ms |
13428 KB |
Output is correct |
| 36 |
Correct |
234 ms |
14072 KB |
Output is correct |
| 37 |
Correct |
271 ms |
15040 KB |
Output is correct |
| 38 |
Correct |
338 ms |
14904 KB |
Output is correct |
| 39 |
Correct |
314 ms |
14712 KB |
Output is correct |
| 40 |
Correct |
421 ms |
16376 KB |
Output is correct |
| 41 |
Correct |
677 ms |
18324 KB |
Output is correct |
