Submission #261479

#	Time	Username	Problem	Language	Result	Execution time	Memory
261479		zecookiez	Triumphal arch (POI13_luk)	C++14	100 / 100	1000 ms	26488 KiB

luk

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
vector<int> adj[MAXN];
int helper(int node, int work, int prev = -1){
    int bleh = 0;
    for(auto i : adj[node]){
        if(i == prev) continue;
        ++bleh; bleh += helper(i, work, node);
    }
    return max(bleh - work, 0);
}
int main(){
    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    for(int a, b, i = 1; i < n; ++i){
        cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a);
    }
    int left = -1, right = n;
    while(right - left > 1){
        int mid = left + (right - left) / 2;
        if(helper(1, mid) != 0) left = mid;
        else right = mid;
    }
    cout << right << '\n';
    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