# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
88875 | 2018-12-09T17:05:14 Z | sailormoon | Triumphal arch (POI13_luk) | C++14 | 1381 ms | 87728 KB |
#include <string> #include <algorithm> #include <iostream> #include <vector> #include <unordered_set> using namespace std; int canHandle(int v, int crs); vector<vector<int>> graph (3000001); // size bool visited[3000001]; int main() { int n, a, b, start = 0, midpoint, end, cities; // n -> towns, a -> from, b -> to scanf("%d", &n); cities = n; // for further usage end = n; // last point n--; while (n--) { 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) { midpoint = (start + end) / 2; for (int i = 0; i < cities; i++) visited[i] = false; // clear array if (canHandle(1, midpoint) == 0) end = midpoint; else start = ++midpoint; } printf("%d\n", start); return 0; } int canHandle(int v, int crs) { int num_children = 0, need_crews = 0; visited[v] = true; for (int i = 0; i < graph[v].size(); i++) { if (!visited[graph[v][i]]) { num_children++; need_crews += canHandle(graph[v][i], crs); } } return max(0, num_children + need_crews - crs); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 70 ms | 70776 KB | Output is correct |
2 | Correct | 67 ms | 70784 KB | Output is correct |
3 | Correct | 70 ms | 70848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 70 ms | 70852 KB | Output is correct |
2 | Correct | 71 ms | 70856 KB | Output is correct |
3 | Correct | 74 ms | 70860 KB | Output is correct |
4 | Incorrect | 73 ms | 70980 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 70 ms | 70980 KB | Output is correct |
2 | Correct | 70 ms | 70980 KB | Output is correct |
3 | Correct | 64 ms | 70980 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 64 ms | 71000 KB | Output is correct |
2 | Correct | 65 ms | 71008 KB | Output is correct |
3 | Correct | 69 ms | 71072 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 78 ms | 71568 KB | Output is correct |
2 | Correct | 80 ms | 71692 KB | Output is correct |
3 | Correct | 77 ms | 71788 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 108 ms | 72628 KB | Output is correct |
2 | Correct | 102 ms | 73668 KB | Output is correct |
3 | Correct | 223 ms | 73668 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 230 ms | 75688 KB | Output is correct |
2 | Correct | 201 ms | 76920 KB | Output is correct |
3 | Correct | 217 ms | 76920 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 721 ms | 79144 KB | Output is correct |
2 | Correct | 544 ms | 83084 KB | Output is correct |
3 | Correct | 258 ms | 83084 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1381 ms | 83244 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1372 ms | 83244 KB | Output is correct |
2 | Correct | 1155 ms | 87728 KB | Output is correct |
3 | Correct | 616 ms | 87728 KB | Output is correct |