# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
88886 | 2018-12-09T18:18:45 Z | zviki | Triumphal arch (POI13_luk) | C++14 | 287 ms | 18768 KB |
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <vector> #define avg(a, b) ((a + b) / 2) #define ARR_SIZE 300050 using namespace std; vector<vector<int>> map_of_cities(ARR_SIZE); int visited_set[ARR_SIZE]; int num_not_satisfy(int num_workers, int city) { int i, child_city, children = map_of_cities[city].size(), rec_res, num_children = 0; visited_set[city] = true; for (i = 0, rec_res = 0; i < children; i++) { child_city = map_of_cities[city][i]; if (visited_set[child_city] == false) { num_children++; rec_res += num_not_satisfy(num_workers, child_city); } } if ((num_children + rec_res - num_workers) <= 0) { return 0; } else { return children + rec_res - num_workers; } } int main() { int n, i, res, bsearch_start, bsearch_end, bsearch_mid, road_from, road_to; scanf("%d", & n); for (i = 1; i < n; i++) { scanf("%d %d", &road_from, & road_to); map_of_cities[road_from].push_back(road_to); map_of_cities[road_to].push_back(road_from); } for (bsearch_start = 0, bsearch_end = n; bsearch_start < bsearch_end; ) { bsearch_mid = avg(bsearch_start, bsearch_end); memset(visited_set, false, ARR_SIZE * sizeof(bool)); res = num_not_satisfy(bsearch_mid, 1); if (res != 0) { bsearch_start = bsearch_mid + 1; } else { bsearch_end = bsearch_mid; } } res = bsearch_start; printf("%d\n", res); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 7672 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 7676 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 12 ms | 7752 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 7752 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 8152 KB | Output is correct |
2 | Correct | 18 ms | 8408 KB | Output is correct |
3 | Incorrect | 13 ms | 8408 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 46 ms | 8964 KB | Output is correct |
2 | Incorrect | 44 ms | 10100 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 71 ms | 11256 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 169 ms | 14996 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 281 ms | 18768 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 287 ms | 18768 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |