| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 88925 | ahaa | 새로운 문제 (POI13_luk) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}