# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
88866 | 2018-12-09T12:00:16 Z | 123456 | Triumphal arch (POI13_luk) | C++14 | 1535 ms | 22808 KB |
#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<vector<int>> graph; vector<bool> visited; int check(int currentCity, int k) { int childrenSum = 0; visited[currentCity] = true; for (int i = 0; i < graph[currentCity].size(); i++) { if (!visited[graph[currentCity][i]]) { childrenSum += check(graph[currentCity][i], k); } } int numberOfChildren = graph[currentCity].size() - 1; if (currentCity == 0) numberOfChildren++; return max(0, numberOfChildren + childrenSum - k); } int main() { int numberOfTowns; cin >> numberOfTowns; if (numberOfTowns < 0) { return 0; } visited.resize(numberOfTowns); graph.resize(numberOfTowns); for (int i = 0; i < numberOfTowns - 1; i++) { int a, b; cin >> a >> b; a--; b--; graph[a].push_back(b); graph[b].push_back(a); } int start = 1; int end = numberOfTowns; int currentK; while (start < end) { for (int i = 0; i < numberOfTowns; i++) { visited[i] = false; } currentK = (start + end) / 2; if (check(0, currentK) == 0) { end = currentK; } else { start = currentK + 1; } } cout << start << endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
2 | Correct | 2 ms | 500 KB | Output is correct |
3 | Correct | 2 ms | 528 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 528 KB | Output is correct |
2 | Correct | 2 ms | 528 KB | Output is correct |
3 | Correct | 2 ms | 528 KB | Output is correct |
4 | Correct | 2 ms | 528 KB | Output is correct |
5 | Incorrect | 2 ms | 528 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 528 KB | Output is correct |
2 | Correct | 2 ms | 540 KB | Output is correct |
3 | Correct | 2 ms | 548 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 576 KB | Output is correct |
2 | Correct | 3 ms | 576 KB | Output is correct |
3 | Correct | 3 ms | 576 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 1088 KB | Output is correct |
2 | Correct | 16 ms | 1384 KB | Output is correct |
3 | Correct | 12 ms | 1384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 56 ms | 2412 KB | Output is correct |
2 | Correct | 54 ms | 3180 KB | Output is correct |
3 | Correct | 37 ms | 3180 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 260 ms | 6308 KB | Output is correct |
2 | Correct | 255 ms | 8092 KB | Output is correct |
3 | Correct | 132 ms | 8092 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 725 ms | 11976 KB | Output is correct |
2 | Correct | 751 ms | 16668 KB | Output is correct |
3 | Correct | 307 ms | 16668 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1407 ms | 17644 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1535 ms | 17648 KB | Output is correct |
2 | Correct | 1392 ms | 22808 KB | Output is correct |
3 | Correct | 612 ms | 22808 KB | Output is correct |