| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 101650 |
2019-03-19T07:11:53 Z |
dwsc |
007 (CEOI14_007) |
C++14 |
|
711 ms |
26744 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 |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Partially correct |
2 ms |
384 KB |
Partially correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
256 KB |
Output is correct |
| 7 |
Correct |
2 ms |
256 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
3 ms |
256 KB |
Output is correct |
| 11 |
Correct |
2 ms |
256 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 13 |
Correct |
3 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 |
2 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 |
0 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 |
3 ms |
384 KB |
Output is correct |
| 24 |
Correct |
3 ms |
380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
3192 KB |
Output is correct |
| 2 |
Incorrect |
65 ms |
4444 KB |
Output isn't correct |
| 3 |
Correct |
68 ms |
3448 KB |
Output is correct |
| 4 |
Incorrect |
78 ms |
4604 KB |
Output isn't correct |
| 5 |
Correct |
73 ms |
3192 KB |
Output is correct |
| 6 |
Correct |
50 ms |
3544 KB |
Output is correct |
| 7 |
Correct |
60 ms |
3832 KB |
Output is correct |
| 8 |
Correct |
53 ms |
3832 KB |
Output is correct |
| 9 |
Incorrect |
104 ms |
5264 KB |
Output isn't correct |
| 10 |
Correct |
417 ms |
18352 KB |
Output is correct |
| 11 |
Incorrect |
135 ms |
6776 KB |
Output isn't correct |
| 12 |
Correct |
189 ms |
8524 KB |
Output is correct |
| 13 |
Incorrect |
127 ms |
7288 KB |
Output isn't correct |
| 14 |
Correct |
115 ms |
6152 KB |
Output is correct |
| 15 |
Correct |
201 ms |
8544 KB |
Output is correct |
| 16 |
Correct |
160 ms |
8952 KB |
Output is correct |
| 17 |
Correct |
158 ms |
7952 KB |
Output is correct |
| 18 |
Incorrect |
166 ms |
8056 KB |
Output isn't correct |
| 19 |
Correct |
238 ms |
11700 KB |
Output is correct |
| 20 |
Incorrect |
612 ms |
20600 KB |
Output isn't correct |
| 21 |
Incorrect |
213 ms |
11740 KB |
Output isn't correct |
| 22 |
Correct |
198 ms |
10144 KB |
Output is correct |
| 23 |
Correct |
200 ms |
11448 KB |
Output is correct |
| 24 |
Correct |
220 ms |
11500 KB |
Output is correct |
| 25 |
Incorrect |
196 ms |
10788 KB |
Output isn't correct |
| 26 |
Correct |
180 ms |
10360 KB |
Output is correct |
| 27 |
Correct |
223 ms |
11640 KB |
Output is correct |
| 28 |
Correct |
233 ms |
11640 KB |
Output is correct |
| 29 |
Correct |
317 ms |
14840 KB |
Output is correct |
| 30 |
Incorrect |
510 ms |
21784 KB |
Output isn't correct |
| 31 |
Incorrect |
240 ms |
13532 KB |
Output isn't correct |
| 32 |
Correct |
217 ms |
11640 KB |
Output is correct |
| 33 |
Correct |
193 ms |
11896 KB |
Output is correct |
| 34 |
Incorrect |
299 ms |
12756 KB |
Output isn't correct |
| 35 |
Incorrect |
230 ms |
12024 KB |
Output isn't correct |
| 36 |
Incorrect |
218 ms |
12408 KB |
Output isn't correct |
| 37 |
Correct |
318 ms |
14200 KB |
Output is correct |
| 38 |
Correct |
268 ms |
13688 KB |
Output is correct |
| 39 |
Correct |
316 ms |
13800 KB |
Output is correct |
| 40 |
Incorrect |
480 ms |
19164 KB |
Output isn't correct |
| 41 |
Correct |
711 ms |
26744 KB |
Output is correct |
