Submission #654062

#	Time	Username	Problem	Language	Result	Execution time	Memory
654062		MasterTaster	Triumphal arch (POI13_luk)	C++14	100 / 100	991 ms	27800 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-1, ress=n-1;
 
    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: 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