# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
88851 | 2018-12-09T08:51:27 Z | sailormoon | Triumphal arch (POI13_luk) | C++14 | 2000 ms | 30308 KB |
#include <map> #include <string> #include <algorithm> #include <iostream> #include <vector> #include <unordered_set> using namespace std; vector<vector<int>> graph (300001); // size unordered_set<int> visited; int canHandle(int v, int crs) { int num_children = 0, need_crews = 0; visited.insert(v); for (int i = 0; i < graph[v].size(); i++) { if (visited.find(graph[v][i]) == visited.end()) { num_children++; need_crews += canHandle(graph[v][i], crs); } } return max(0, num_children + need_crews - crs); } int main() { int n, a, b, start = 0, midpoint, end; // n -> towns, a -> from, b -> to scanf("%d", &n); 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; if (canHandle(1, midpoint) == 0) end = midpoint; else start = ++midpoint; visited.clear(); } printf("%d\n", start); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 7416 KB | Output is correct |
2 | Correct | 7 ms | 7420 KB | Output is correct |
3 | Correct | 7 ms | 7496 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7624 KB | Output is correct |
2 | Correct | 7 ms | 7624 KB | Output is correct |
3 | Correct | 7 ms | 7624 KB | Output is correct |
4 | Correct | 7 ms | 7624 KB | Output is correct |
5 | Correct | 9 ms | 7624 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 7744 KB | Output is correct |
2 | Correct | 7 ms | 7744 KB | Output is correct |
3 | Correct | 8 ms | 7744 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 7744 KB | Output is correct |
2 | Correct | 9 ms | 7744 KB | Output is correct |
3 | Correct | 9 ms | 7744 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 32 ms | 8316 KB | Output is correct |
2 | Correct | 33 ms | 8444 KB | Output is correct |
3 | Correct | 26 ms | 8444 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 263 ms | 9980 KB | Output is correct |
2 | Correct | 92 ms | 10620 KB | Output is correct |
3 | Correct | 82 ms | 10620 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 652 ms | 14860 KB | Output is correct |
2 | Correct | 780 ms | 16268 KB | Output is correct |
3 | Correct | 503 ms | 16268 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1966 ms | 22240 KB | Output is correct |
2 | Correct | 1494 ms | 25724 KB | Output is correct |
3 | Correct | 885 ms | 25724 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2057 ms | 30308 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2029 ms | 30308 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |