| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 118457 |
2019-06-19T04:00:06 Z |
minhtung0404 |
007 (CEOI14_007) |
C++17 |
|
303 ms |
25208 KB |
//https://oj.uz/problem/view/CEOI14_007
#include<bits/stdc++.h>
const int N = 2e5 + 5;
using namespace std;
vector <int> G[N];
int n, m, p[2], a[2];
int d[2][N], d2[N], Max[N];
bool ck[N];
void bfs(int u, int t){
queue <int> mq; mq.push(u); d[t][u] = 1;
while (mq.size()){
u = mq.front(); mq.pop();
for (auto v : G[u]){
if (!d[t][v]){
d[t][v] = d[t][u] + 1;
mq.push(v);
}
}
}
}
void dfs(int u){
Max[u] = 1;
for (auto v : G[u]){
if (d[0][v] + 1 == d[0][u] && d[1][v] + 1 == d[1][u]){
if (!Max[v]) dfs(v);
Max[u] = max(Max[u], Max[v] + 1);
}
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
cin >> p[0] >> p[1] >> a[0] >> a[1];
while (m--){
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
bfs(a[0], 0); bfs(a[1], 1);
for (int i = 1; i <= n; i++){
if (d[0][i] < d[0][p[0]] || d[1][i] < d[1][p[0]]) ck[i] = true;
}
if (d[0][p[0]] == d[1][p[0]]){
for (int i = 1; i <= n; i++){
if (d[0][i] == d[1][i] && d[0][i] == d[0][p[0]] && !Max[i]) dfs(i);
}
for (int i = 1; i <= n; i++) if (Max[i] > Max[p[0]]) ck[i] = true;
}
queue <int> mq; mq.push(p[1]); d2[p[1]] = 1;
while (mq.size()){
int u = mq.front(); mq.pop();
if (ck[u]) return cout << d2[u] - 2, 0;
for (auto v : G[u]){
if (!d2[v]){
d2[v] = d2[u] + 1;
mq.push(v);
}
}
}
}
/*
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 4 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 6 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 7 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 8 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 9 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 10 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 11 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 12 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 13 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 14 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 15 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 16 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 17 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 18 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 19 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 20 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 21 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 22 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 23 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 24 |
Correct |
6 ms |
5120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
7040 KB |
Output is correct |
| 2 |
Correct |
35 ms |
8064 KB |
Output is correct |
| 3 |
Correct |
25 ms |
7032 KB |
Output is correct |
| 4 |
Correct |
40 ms |
8184 KB |
Output is correct |
| 5 |
Correct |
28 ms |
6776 KB |
Output is correct |
| 6 |
Correct |
23 ms |
7032 KB |
Output is correct |
| 7 |
Correct |
31 ms |
7288 KB |
Output is correct |
| 8 |
Correct |
28 ms |
7296 KB |
Output is correct |
| 9 |
Correct |
44 ms |
7800 KB |
Output is correct |
| 10 |
Correct |
159 ms |
12404 KB |
Output is correct |
| 11 |
Correct |
60 ms |
9464 KB |
Output is correct |
| 12 |
Correct |
105 ms |
11768 KB |
Output is correct |
| 13 |
Correct |
66 ms |
9336 KB |
Output is correct |
| 14 |
Correct |
55 ms |
8696 KB |
Output is correct |
| 15 |
Correct |
87 ms |
12012 KB |
Output is correct |
| 16 |
Correct |
91 ms |
12024 KB |
Output is correct |
| 17 |
Correct |
69 ms |
11260 KB |
Output is correct |
| 18 |
Correct |
66 ms |
11384 KB |
Output is correct |
| 19 |
Correct |
111 ms |
14072 KB |
Output is correct |
| 20 |
Correct |
209 ms |
19832 KB |
Output is correct |
| 21 |
Correct |
106 ms |
15096 KB |
Output is correct |
| 22 |
Correct |
105 ms |
13052 KB |
Output is correct |
| 23 |
Correct |
102 ms |
13944 KB |
Output is correct |
| 24 |
Correct |
109 ms |
14584 KB |
Output is correct |
| 25 |
Correct |
109 ms |
13944 KB |
Output is correct |
| 26 |
Correct |
95 ms |
13048 KB |
Output is correct |
| 27 |
Correct |
108 ms |
13996 KB |
Output is correct |
| 28 |
Correct |
123 ms |
14200 KB |
Output is correct |
| 29 |
Correct |
166 ms |
16628 KB |
Output is correct |
| 30 |
Correct |
226 ms |
21008 KB |
Output is correct |
| 31 |
Correct |
127 ms |
16760 KB |
Output is correct |
| 32 |
Correct |
127 ms |
14456 KB |
Output is correct |
| 33 |
Correct |
109 ms |
14392 KB |
Output is correct |
| 34 |
Correct |
124 ms |
15480 KB |
Output is correct |
| 35 |
Correct |
122 ms |
15480 KB |
Output is correct |
| 36 |
Correct |
105 ms |
15736 KB |
Output is correct |
| 37 |
Correct |
140 ms |
16120 KB |
Output is correct |
| 38 |
Correct |
150 ms |
15608 KB |
Output is correct |
| 39 |
Correct |
153 ms |
16248 KB |
Output is correct |
| 40 |
Correct |
224 ms |
20344 KB |
Output is correct |
| 41 |
Correct |
303 ms |
25208 KB |
Output is correct |
