# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
88910 | 2018-12-09T19:02:02 Z | sailormoon | Triumphal arch (POI13_luk) | C++14 | 1215 ms | 39484 KB |
#include <string> #include <algorithm> #include <iostream> #include <vector> using namespace std; int can_handle(int v, int crs, bool visited[]); vector<vector<int>> graph (1000001); // size int main() { int n, a, b, start = 0, midpoint, end, cities; // n -> towns, a -> from, b -> to scanf("%d", &n); end = n; // last point for (int i = 1; i < n; i++) { scanf("%d %d", &a, &b); graph[a].push_back(b); graph[b].push_back(a); } // binary search for sufficient amount of crews while (start < end) { bool visited[1000001]; midpoint = (start + end) / 2; for (int i = 1; i <= n; i++) visited[i] = false; // clear array if (can_handle(1, midpoint, visited) == 0) end = midpoint; else start = ++midpoint; } printf("%d\n", start); return 0; } int can_handle(int v, int crs, bool visited[]) { int num_children = 0, need_crews = 0; visited[v] = true; for (int i = 0; i < graph[v].size(); i++) { int cur = graph[v][i]; if (!visited[cur]) { num_children++; need_crews += can_handle(cur, crs, visited); } } if (num_children + need_crews - crs <= 0) return 0; return num_children + need_crews - crs; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 23928 KB | Output is correct |
2 | Correct | 25 ms | 23932 KB | Output is correct |
3 | Correct | 27 ms | 23932 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 23932 KB | Output is correct |
2 | Correct | 27 ms | 23932 KB | Output is correct |
3 | Correct | 25 ms | 24036 KB | Output is correct |
4 | Correct | 25 ms | 24036 KB | Output is correct |
5 | Correct | 25 ms | 24140 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 24140 KB | Output is correct |
2 | Correct | 27 ms | 24140 KB | Output is correct |
3 | Correct | 25 ms | 24140 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 28 ms | 24140 KB | Output is correct |
2 | Correct | 28 ms | 24140 KB | Output is correct |
3 | Correct | 30 ms | 24140 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 24556 KB | Output is correct |
2 | Correct | 36 ms | 24556 KB | Output is correct |
3 | Correct | 30 ms | 24556 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 65 ms | 25212 KB | Output is correct |
2 | Correct | 60 ms | 25980 KB | Output is correct |
3 | Correct | 43 ms | 25980 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 172 ms | 27540 KB | Output is correct |
2 | Correct | 171 ms | 29368 KB | Output is correct |
3 | Correct | 88 ms | 29368 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 600 ms | 30944 KB | Output is correct |
2 | Correct | 554 ms | 35464 KB | Output is correct |
3 | Correct | 219 ms | 35464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 969 ms | 35464 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1047 ms | 35464 KB | Output is correct |
2 | Correct | 1215 ms | 39484 KB | Output is correct |
3 | Correct | 419 ms | 39484 KB | Output is correct |