| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 88925 | ahaa | Triumphal arch (POI13_luk) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#define avg(a, b) ((a + b) / 2)
vector<vector<int>> treeOfCities;
int numMoreWorkersNeeded(bool[] visited, int currWorkers, int currCity){
visited[currCity] = true;
int numChildren = treeOfCities[currCity].size();
int childResSum = 0;
int unBuildChildren = 0;
for(int i = 0; i < numChildren; i++){
int currChild = treeOfCities[currCity][i];
if(!visited[currChild]){
unBuildChildren++;
childResSum += numMoreWorkersNeeded(visited, currWorkers, currChild);
}
}
if(currWorkers > unBuildChildren + childResSum){
return 0;
}else {
return unBuildChildren + childResSum - currWorkers;
}
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
vector<int> v;
treeOfCities.push_back(v);
}
int from;
int to;
for(int i = 0; i < n-1; i++){
cin >> from >> to;
treeOfCities[from - 1].push_back(to - 1);
treeOfCities[to - 1].push_back(from - 1);
}
int start = 0;
int end = n;
int result = 0;
while(start < end){
int middle = avg(start, end);
bool visited[n+10] = { false };
result = numMoreWorkersNeeded(visited, middle, 0);
if(result != 0){
start = middle + 1;
}else {
end = middle;
}
}
result = start;
cout << result << endl;
return 0;
}