# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
88901 | 2018-12-09T18:48:06 Z | sailormoon | Triumphal arch (POI13_luk) | C++14 | 1135 ms | 38124 KB |
#include <string> #include <algorithm> #include <iostream> #include <vector> using namespace std; int canHandle(int v, int crs); vector<vector<int>> graph (1000001); // size bool visited[1000001]; 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 + 1; } 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); } } if (num_children + need_crews - crs <= 0) return 0; return num_children + need_crews - crs; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 23800 KB | Output is correct |
2 | Correct | 21 ms | 23924 KB | Output is correct |
3 | Correct | 22 ms | 23992 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 23992 KB | Output is correct |
2 | Correct | 26 ms | 24104 KB | Output is correct |
3 | Correct | 25 ms | 24104 KB | Output is correct |
4 | Incorrect | 22 ms | 24104 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 24104 KB | Output is correct |
2 | Correct | 23 ms | 24104 KB | Output is correct |
3 | Correct | 22 ms | 24104 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 24104 KB | Output is correct |
2 | Correct | 22 ms | 24104 KB | Output is correct |
3 | Correct | 22 ms | 24104 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 31 ms | 24348 KB | Output is correct |
2 | Correct | 30 ms | 24684 KB | Output is correct |
3 | Correct | 27 ms | 24684 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 56 ms | 25084 KB | Output is correct |
2 | Correct | 56 ms | 25792 KB | Output is correct |
3 | Correct | 39 ms | 25792 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 155 ms | 27644 KB | Output is correct |
2 | Correct | 143 ms | 28924 KB | Output is correct |
3 | Correct | 87 ms | 28924 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 553 ms | 30844 KB | Output is correct |
2 | Correct | 584 ms | 34284 KB | Output is correct |
3 | Correct | 230 ms | 34284 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1135 ms | 34360 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1070 ms | 34428 KB | Output is correct |
2 | Correct | 968 ms | 38124 KB | Output is correct |
3 | Correct | 504 ms | 38124 KB | Output is correct |