| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 101481 |
2019-03-19T03:05:57 Z |
dwsc |
007 (CEOI14_007) |
C++14 |
|
748 ms |
26872 KB |
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
vector<int> adj[m];
int s,d,a,b;
cin >> s >> d >> a >> b;
s--;
d--;
a--;
b--;
for (int i = 0; i < m; i++){
int x,y;
cin >> x >> y;
x--;
y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
queue<int> q;
int p1[n],p2[n];
int dist1[n],dist2[n];
memset(dist1,-1,sizeof(dist1));
memset(dist2,-1,sizeof(dist2));
dist1[s] = 0;
dist2[d] = 0;
q.push(s);
while (!q.empty()){
int u = q.front();
q.pop();
for (int i = 0; i < adj[u].size(); i++){
int v = adj[u][i];
if (dist1[v] == -1){
dist1[v] = dist1[u]+1;
q.push(v);
p1[v] = u;
}
}
}
q.push(d);
while (!q.empty()){
int u = q.front();
q.pop();
for (int i = 0; i < adj[u].size(); i++){
int v = adj[u][i];
if (dist2[v] == -1){
dist2[v] = dist2[u]+1;
q.push(v);
p2[v] = u;
}
else if (dist2[u]+1 == dist2[v]) p2[v] = u;
}
}
// cout << dist1[a] << " " << dist1[b] << "\n";
// cout << dist2[a] << " " << dist2[b] << "\n";
if (dist2[a] < dist1[a] && dist2[b] < dist1[b]) cout << -1;
else{
if (dist1[a] > dist1[b]){
swap(dist1[a],dist1[b]);
swap(dist2[a],dist2[b]);
}
if (dist1[a] == dist1[b]){
if (dist2[a] == dist2[b]){
int fin1s = a,fin2s = b;
int fin1d = a,fin2d = b;
int num1 = 0,num2 = 0;
while (fin1s != fin2s){
fin1s = p1[fin1s];
fin2s = p1[fin2s];
num1++;
}
while (fin1d != fin2d){
fin1d = p2[fin1d];
fin2d = p2[fin2d];
num2++;
}
cout << dist2[a]-dist1[a]-(num2<num1);
}
else if (dist2[a]+1 == dist2[b]) cout << dist2[a] - dist1[a];
else cout << dist2[b] - dist1[b];
}
else if (dist1[a]+1 == dist1[b]){
if (dist2[a] == dist2[b]) cout << dist2[b] - dist1[b];
else if (dist2[a] +1 == dist2[b]) cout << dist2[a] - dist1[a];
else cout << dist2[b] - dist1[b];
}
}
}/*
6 6
1 2 3 4
1 5
5 6
6 3
6 4
1 2
3 4
6 7
5 6 1 2
6 3
1 2
1 3
2 3
1 5
2 4
5 4
*/
Compilation message
007.cpp: In function 'int main()':
007.cpp:32:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < adj[u].size(); i++){
~~^~~~~~~~~~~~~~~
007.cpp:45:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < adj[u].size(); i++){
~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 6 |
Correct |
3 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
2 ms |
256 KB |
Output is correct |
| 9 |
Correct |
2 ms |
256 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Correct |
2 ms |
256 KB |
Output is correct |
| 12 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 13 |
Correct |
3 ms |
384 KB |
Output is correct |
| 14 |
Correct |
2 ms |
256 KB |
Output is correct |
| 15 |
Correct |
2 ms |
384 KB |
Output is correct |
| 16 |
Correct |
3 ms |
384 KB |
Output is correct |
| 17 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 18 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 19 |
Correct |
3 ms |
384 KB |
Output is correct |
| 20 |
Correct |
3 ms |
384 KB |
Output is correct |
| 21 |
Correct |
3 ms |
384 KB |
Output is correct |
| 22 |
Correct |
3 ms |
384 KB |
Output is correct |
| 23 |
Correct |
3 ms |
384 KB |
Output is correct |
| 24 |
Correct |
3 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
3196 KB |
Output is correct |
| 2 |
Incorrect |
68 ms |
4472 KB |
Output isn't correct |
| 3 |
Correct |
60 ms |
3420 KB |
Output is correct |
| 4 |
Incorrect |
80 ms |
4692 KB |
Output isn't correct |
| 5 |
Correct |
43 ms |
3192 KB |
Output is correct |
| 6 |
Correct |
47 ms |
3448 KB |
Output is correct |
| 7 |
Correct |
59 ms |
3712 KB |
Output is correct |
| 8 |
Correct |
52 ms |
3832 KB |
Output is correct |
| 9 |
Correct |
92 ms |
5152 KB |
Output is correct |
| 10 |
Correct |
412 ms |
18168 KB |
Output is correct |
| 11 |
Incorrect |
118 ms |
6808 KB |
Output isn't correct |
| 12 |
Correct |
146 ms |
8748 KB |
Output is correct |
| 13 |
Incorrect |
118 ms |
7320 KB |
Output isn't correct |
| 14 |
Correct |
97 ms |
6196 KB |
Output is correct |
| 15 |
Correct |
145 ms |
8580 KB |
Output is correct |
| 16 |
Correct |
165 ms |
9000 KB |
Output is correct |
| 17 |
Correct |
170 ms |
7996 KB |
Output is correct |
| 18 |
Correct |
142 ms |
8112 KB |
Output is correct |
| 19 |
Correct |
292 ms |
11748 KB |
Output is correct |
| 20 |
Correct |
470 ms |
20524 KB |
Output is correct |
| 21 |
Incorrect |
206 ms |
11640 KB |
Output isn't correct |
| 22 |
Correct |
182 ms |
10188 KB |
Output is correct |
| 23 |
Correct |
204 ms |
11496 KB |
Output is correct |
| 24 |
Correct |
213 ms |
11368 KB |
Output is correct |
| 25 |
Incorrect |
271 ms |
10828 KB |
Output isn't correct |
| 26 |
Correct |
172 ms |
10204 KB |
Output is correct |
| 27 |
Correct |
220 ms |
11640 KB |
Output is correct |
| 28 |
Correct |
245 ms |
11632 KB |
Output is correct |
| 29 |
Correct |
374 ms |
14704 KB |
Output is correct |
| 30 |
Correct |
564 ms |
21636 KB |
Output is correct |
| 31 |
Incorrect |
266 ms |
13260 KB |
Output isn't correct |
| 32 |
Correct |
258 ms |
11572 KB |
Output is correct |
| 33 |
Correct |
282 ms |
11896 KB |
Output is correct |
| 34 |
Incorrect |
296 ms |
12664 KB |
Output isn't correct |
| 35 |
Incorrect |
235 ms |
11920 KB |
Output isn't correct |
| 36 |
Incorrect |
279 ms |
12408 KB |
Output isn't correct |
| 37 |
Correct |
265 ms |
13988 KB |
Output is correct |
| 38 |
Correct |
358 ms |
13688 KB |
Output is correct |
| 39 |
Correct |
293 ms |
13848 KB |
Output is correct |
| 40 |
Correct |
453 ms |
19236 KB |
Output is correct |
| 41 |
Correct |
748 ms |
26872 KB |
Output is correct |
