| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 105822 |
2019-04-15T07:58:24 Z |
Bodo171 |
007 (CEOI14_007) |
C++14 |
|
668 ms |
18404 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]);
}
ans=min(d[1][a]-d[0][a]-(d[0][a]==d[0][b]&&det_s>det_t),d[1][b]-d[0][b]-(d[0][b]==d[0][a]&&det_s>det_t));
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 |
4992 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 4 |
Correct |
19 ms |
5120 KB |
Output is correct |
| 5 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 6 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 7 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 8 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 9 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 10 |
Correct |
8 ms |
5120 KB |
Output is correct |
| 11 |
Partially correct |
6 ms |
5120 KB |
Partially correct |
| 12 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 13 |
Correct |
7 ms |
5120 KB |
Output is correct |
| 14 |
Correct |
7 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 |
7 ms |
5120 KB |
Output is correct |
| 18 |
Correct |
9 ms |
5092 KB |
Output is correct |
| 19 |
Correct |
7 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 |
7 ms |
5120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
7060 KB |
Output is correct |
| 2 |
Correct |
70 ms |
8056 KB |
Output is correct |
| 3 |
Correct |
63 ms |
7172 KB |
Output is correct |
| 4 |
Correct |
76 ms |
8184 KB |
Output is correct |
| 5 |
Correct |
61 ms |
7000 KB |
Output is correct |
| 6 |
Correct |
51 ms |
7288 KB |
Output is correct |
| 7 |
Correct |
61 ms |
7544 KB |
Output is correct |
| 8 |
Correct |
62 ms |
7572 KB |
Output is correct |
| 9 |
Correct |
116 ms |
7928 KB |
Output is correct |
| 10 |
Correct |
486 ms |
12408 KB |
Output is correct |
| 11 |
Correct |
123 ms |
9628 KB |
Output is correct |
| 12 |
Correct |
170 ms |
10872 KB |
Output is correct |
| 13 |
Correct |
114 ms |
10028 KB |
Output is correct |
| 14 |
Correct |
95 ms |
9184 KB |
Output is correct |
| 15 |
Correct |
179 ms |
11128 KB |
Output is correct |
| 16 |
Correct |
145 ms |
11256 KB |
Output is correct |
| 17 |
Correct |
133 ms |
10516 KB |
Output is correct |
| 18 |
Correct |
173 ms |
10632 KB |
Output is correct |
| 19 |
Correct |
254 ms |
11768 KB |
Output is correct |
| 20 |
Correct |
447 ms |
14812 KB |
Output is correct |
| 21 |
Correct |
216 ms |
13176 KB |
Output is correct |
| 22 |
Correct |
188 ms |
12140 KB |
Output is correct |
| 23 |
Correct |
217 ms |
13176 KB |
Output is correct |
| 24 |
Correct |
207 ms |
13088 KB |
Output is correct |
| 25 |
Correct |
199 ms |
12660 KB |
Output is correct |
| 26 |
Correct |
184 ms |
12280 KB |
Output is correct |
| 27 |
Correct |
191 ms |
13220 KB |
Output is correct |
| 28 |
Correct |
234 ms |
13352 KB |
Output is correct |
| 29 |
Correct |
289 ms |
13672 KB |
Output is correct |
| 30 |
Correct |
575 ms |
15584 KB |
Output is correct |
| 31 |
Correct |
238 ms |
14468 KB |
Output is correct |
| 32 |
Correct |
237 ms |
13048 KB |
Output is correct |
| 33 |
Correct |
197 ms |
13432 KB |
Output is correct |
| 34 |
Correct |
248 ms |
13816 KB |
Output is correct |
| 35 |
Correct |
235 ms |
13540 KB |
Output is correct |
| 36 |
Correct |
228 ms |
13816 KB |
Output is correct |
| 37 |
Correct |
288 ms |
14960 KB |
Output is correct |
| 38 |
Correct |
285 ms |
14652 KB |
Output is correct |
| 39 |
Correct |
321 ms |
14780 KB |
Output is correct |
| 40 |
Correct |
412 ms |
16248 KB |
Output is correct |
| 41 |
Correct |
668 ms |
18404 KB |
Output is correct |
