| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 101649 |
2019-03-19T07:11:15 Z |
dwsc |
007 (CEOI14_007) |
C++14 |
|
743 ms |
27464 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;
}
}
}
// 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+dist2[a]-dist1[a]<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 |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 6 |
Correct |
3 ms |
256 KB |
Output is correct |
| 7 |
Correct |
3 ms |
384 KB |
Output is correct |
| 8 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 9 |
Correct |
3 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Correct |
3 ms |
384 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 15 |
Correct |
3 ms |
384 KB |
Output is correct |
| 16 |
Incorrect |
3 ms |
384 KB |
Output isn't 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 |
2 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 |
2 ms |
384 KB |
Output is correct |
| 24 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
3648 KB |
Output is correct |
| 2 |
Incorrect |
65 ms |
4856 KB |
Output isn't correct |
| 3 |
Correct |
49 ms |
3832 KB |
Output is correct |
| 4 |
Incorrect |
80 ms |
5140 KB |
Output isn't correct |
| 5 |
Correct |
55 ms |
3448 KB |
Output is correct |
| 6 |
Correct |
53 ms |
3960 KB |
Output is correct |
| 7 |
Correct |
57 ms |
4088 KB |
Output is correct |
| 8 |
Correct |
59 ms |
4216 KB |
Output is correct |
| 9 |
Incorrect |
91 ms |
5492 KB |
Output isn't correct |
| 10 |
Correct |
532 ms |
19076 KB |
Output is correct |
| 11 |
Incorrect |
110 ms |
7236 KB |
Output isn't correct |
| 12 |
Correct |
167 ms |
8952 KB |
Output is correct |
| 13 |
Incorrect |
121 ms |
7672 KB |
Output isn't correct |
| 14 |
Correct |
95 ms |
6524 KB |
Output is correct |
| 15 |
Correct |
188 ms |
8984 KB |
Output is correct |
| 16 |
Correct |
157 ms |
9208 KB |
Output is correct |
| 17 |
Correct |
126 ms |
8316 KB |
Output is correct |
| 18 |
Incorrect |
227 ms |
8440 KB |
Output isn't correct |
| 19 |
Correct |
246 ms |
12280 KB |
Output is correct |
| 20 |
Incorrect |
515 ms |
21372 KB |
Output isn't correct |
| 21 |
Incorrect |
260 ms |
12280 KB |
Output isn't correct |
| 22 |
Correct |
235 ms |
10872 KB |
Output is correct |
| 23 |
Correct |
238 ms |
12088 KB |
Output is correct |
| 24 |
Correct |
231 ms |
12048 KB |
Output is correct |
| 25 |
Incorrect |
179 ms |
11388 KB |
Output isn't correct |
| 26 |
Correct |
177 ms |
11016 KB |
Output is correct |
| 27 |
Correct |
237 ms |
12280 KB |
Output is correct |
| 28 |
Correct |
247 ms |
12408 KB |
Output is correct |
| 29 |
Correct |
384 ms |
15600 KB |
Output is correct |
| 30 |
Incorrect |
556 ms |
22520 KB |
Output isn't correct |
| 31 |
Incorrect |
267 ms |
13924 KB |
Output isn't correct |
| 32 |
Correct |
253 ms |
12280 KB |
Output is correct |
| 33 |
Correct |
230 ms |
12536 KB |
Output is correct |
| 34 |
Incorrect |
248 ms |
13296 KB |
Output isn't correct |
| 35 |
Incorrect |
247 ms |
12792 KB |
Output isn't correct |
| 36 |
Incorrect |
224 ms |
13048 KB |
Output isn't correct |
| 37 |
Correct |
287 ms |
14712 KB |
Output is correct |
| 38 |
Correct |
283 ms |
14428 KB |
Output is correct |
| 39 |
Correct |
380 ms |
14428 KB |
Output is correct |
| 40 |
Incorrect |
445 ms |
20088 KB |
Output isn't correct |
| 41 |
Correct |
743 ms |
27464 KB |
Output is correct |
