oj.uz

Submission #88926

# Submission time Handle Problem Language Result Execution time Memory
88926 2018-12-09T22:17:56 Z ahaa Triumphal arch (POI13_luk) C++14
100 / 100
 1285 ms 24620 KB 
#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.0 / 10.0

# 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 500 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 500 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 548 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 560 KB Output is correct
2 Correct 2 ms 568 KB Output is correct
3 Correct 2 ms 584 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 592 KB Output is correct
2 Correct 3 ms 672 KB Output is correct
3 Correct 3 ms 672 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1132 KB Output is correct
2 Correct 16 ms 1512 KB Output is correct
3 Correct 12 ms 1512 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2288 KB Output is correct
2 Correct 51 ms 3464 KB Output is correct
3 Correct 37 ms 3464 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 6360 KB Output is correct
2 Correct 218 ms 8648 KB Output is correct
3 Correct 125 ms 8648 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 12152 KB Output is correct
2 Correct 704 ms 18012 KB Output is correct
3 Correct 303 ms 18012 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1285 ms 18012 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1266 ms 18012 KB Output is correct
2 Correct 1261 ms 24620 KB Output is correct
3 Correct 647 ms 24620 KB Output is correct