| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 974747 |
2024-05-03T17:57:20 Z |
Nalrimet |
007 (CEOI14_007) |
C++17 |
|
333 ms |
27560 KB |
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
std::vector<std::vector<int>> init_graph(int n, const std::vector<std::pair<int, int>>& edges) {
std::vector<std::vector<int>> graph(n + 1);
for (auto& edge : edges) {
graph[edge.first].push_back(edge.second);
graph[edge.second].push_back(edge.first);
}
return graph;
}
std::vector<int> bfs(const std::vector<std::vector<int>>& graph, int start) {
std::vector<int> distances(graph.size(), -1);
std::queue<int> q;
q.push(start);
distances[start] = 0;
while (!q.empty()) {
int current = q.front();
q.pop();
for (int neighbor : graph[current]) {
if (distances[neighbor] == -1) {
distances[neighbor] = distances[current] + 1;
q.push(neighbor);
}
}
}
return distances;
}
int main() {
int N, M, s, d, a, b;
std::cin >> N >> M;
std::cin >> s >> d >> a >> b;
std::vector<std::pair<int, int>> edges(M);
for (int i = 0; i < M; ++i) {
std::cin >> edges[i].first >> edges[i].second;
}
auto graph = init_graph(N, edges);
auto distances_s = bfs(graph, s);
auto distances_d = bfs(graph, d);
int a1 = distances_s[a], a2 = distances_s[b];
int b1 = distances_d[a], b2 = distances_d[b];
int w1 = b1 - a1, w2 = b2 - a2;
// Стратегия для определения максимального времени ожидания
int max_wait_time = -1;
if ((w1 < 0 && w2 < 0) || (a1 == -1 && a2 == -1)) {
max_wait_time = -1; // 007 не может вообще победить, если она не достигает серверов
} else {
if (w1 == w2) {
max_wait_time = std::max(0, w1); // Максимальное время ожидания равно минимальному w
} else {
max_wait_time = std::max(0, std::min(w1, w2)); // Берем минимальное значение w
}
}
std::cout << max_wait_time << std::endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
416 KB |
Output isn't correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
432 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 17 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 18 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 19 |
Correct |
1 ms |
348 KB |
Output is correct |
| 20 |
Correct |
1 ms |
344 KB |
Output is correct |
| 21 |
Correct |
1 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
344 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
3676 KB |
Output is correct |
| 2 |
Incorrect |
36 ms |
5160 KB |
Output isn't correct |
| 3 |
Correct |
26 ms |
3920 KB |
Output is correct |
| 4 |
Incorrect |
34 ms |
5468 KB |
Output isn't correct |
| 5 |
Correct |
25 ms |
3668 KB |
Output is correct |
| 6 |
Correct |
25 ms |
3932 KB |
Output is correct |
| 7 |
Correct |
28 ms |
4440 KB |
Output is correct |
| 8 |
Correct |
28 ms |
4432 KB |
Output is correct |
| 9 |
Incorrect |
48 ms |
5452 KB |
Output isn't correct |
| 10 |
Correct |
248 ms |
17440 KB |
Output is correct |
| 11 |
Incorrect |
52 ms |
7760 KB |
Output isn't correct |
| 12 |
Correct |
71 ms |
9808 KB |
Output is correct |
| 13 |
Incorrect |
62 ms |
8520 KB |
Output isn't correct |
| 14 |
Correct |
50 ms |
7092 KB |
Output is correct |
| 15 |
Correct |
67 ms |
9860 KB |
Output is correct |
| 16 |
Correct |
76 ms |
10480 KB |
Output is correct |
| 17 |
Correct |
61 ms |
9300 KB |
Output is correct |
| 18 |
Incorrect |
63 ms |
9300 KB |
Output isn't correct |
| 19 |
Correct |
124 ms |
12588 KB |
Output is correct |
| 20 |
Incorrect |
244 ms |
20564 KB |
Output isn't correct |
| 21 |
Incorrect |
94 ms |
13592 KB |
Output isn't correct |
| 22 |
Correct |
85 ms |
11904 KB |
Output is correct |
| 23 |
Correct |
92 ms |
13420 KB |
Output is correct |
| 24 |
Correct |
109 ms |
13412 KB |
Output is correct |
| 25 |
Incorrect |
90 ms |
12660 KB |
Output isn't correct |
| 26 |
Correct |
82 ms |
11888 KB |
Output is correct |
| 27 |
Correct |
113 ms |
13564 KB |
Output is correct |
| 28 |
Correct |
97 ms |
13652 KB |
Output is correct |
| 29 |
Correct |
152 ms |
16000 KB |
Output is correct |
| 30 |
Incorrect |
270 ms |
21892 KB |
Output isn't correct |
| 31 |
Incorrect |
109 ms |
15564 KB |
Output isn't correct |
| 32 |
Correct |
108 ms |
13472 KB |
Output is correct |
| 33 |
Correct |
96 ms |
13860 KB |
Output is correct |
| 34 |
Incorrect |
138 ms |
14608 KB |
Output isn't correct |
| 35 |
Incorrect |
104 ms |
14324 KB |
Output isn't correct |
| 36 |
Incorrect |
107 ms |
14660 KB |
Output isn't correct |
| 37 |
Correct |
118 ms |
16468 KB |
Output is correct |
| 38 |
Correct |
126 ms |
15980 KB |
Output is correct |
| 39 |
Correct |
115 ms |
16208 KB |
Output is correct |
| 40 |
Incorrect |
228 ms |
20832 KB |
Output isn't correct |
| 41 |
Correct |
333 ms |
27560 KB |
Output is correct |
