Submission #491073

#	Time	Username	Problem	Language	Result	Execution time	Memory
491073		MasterTaster	Triumphal arch (POI13_luk)	C++14	90 / 100	996 ms	27772 KiB

luk

#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXN 300010

using namespace std;

int k, n, dp[MAXN];
bool bio[MAXN];
vector<int> g[MAXN];

void dfs(int u)
{
    bio[u]=true;

    for (auto v:g[u])
    {
        if (!bio[v])
        {
            dfs(v);
            dp[u]+=(dp[v]+1);
        }
    }
    dp[u]-=k;
    dp[u]=max(dp[u], 0);
}

bool check(int x)
{
    k=x;
    for (int i=1; i<=n; i++) { bio[i]=false; dp[i]=0; }
    dfs(1);
    if (dp[1]<=0) return true;
    else return false;
}

void bs()
{
    int l=1, r=n, ress=n;

    while (l<=r)
    {
        int mid=l+(r-l)/2;
        if (check(mid)) { ress=mid; r=mid-1; }
        else l=mid+1;
    }

    cout<<ress;
}

int main()
{
    cin>>n;

    for (int i=1; i<n; i++)
    {
        int u, v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }

    bs();
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 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