# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
88888 | 2018-12-09T18:20:45 Z | zviki | Triumphal arch (POI13_luk) | C++14 | 18 ms | 2340 KB |
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <vector> #define avg(a, b) ((a + b) / 2) #define ARR_SIZE 30005 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 | 3 ms | 1016 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 1152 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 1152 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 1228 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 7 ms | 1668 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 18 ms | 2340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 2340 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 4 ms | 2340 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 2 ms | 2340 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 3 ms | 2340 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |