Submission #88926

#	Time	Username	Problem	Language	Result	Execution time	Memory
88926		ahaa	Triumphal arch (POI13_luk)	C++14	100 / 100	1285 ms	24620 KiB

luk

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>
using namespace std;

#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;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10