제출 #505099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
505099		tgbegimx	무제 (POI11_dyn)	C++14	100 / 100	695 ms	28308 KiB

Main

#include <bits/stdc++.h>
#define ll int
using namespace std;
ll n,m,l,r,mid,dem,res=300005,mx[300005],mi[300005],cha[300005],i;
bool dd[300005];
vector<ll> luu;
vector<vector<ll> > a;
void dfs1(ll u,ll p)
{
    luu.push_back(u);
    cha[u]=p;
    for(auto v:a[u])
    {
        if(v!=p) dfs1(v,u);
    }
}
void dfs2()
{
    for(ll i=n-1;i>=0;i--)
    {
        ll u=luu[i];
        mx[u]=-1e9;mi[u]=1e9;
        for(auto v:a[u])
        {
            if(v!=cha[u])
            {
                mx[u]=max(mx[u],mx[v]+1);
                mi[u]=min(mi[u],mi[v]+1);
            }
        }
        if(mi[u]>mid&&dd[u]) mx[u]=max(mx[u],0);
        if(mi[u]+mx[u]<=mid) mx[u]=-1e9;
        if(mx[u]==mid) {mx[u]=-1e9;mi[u]=0;dem++;}
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        ll k;
        cin>>k;
        if(k==1) dd[i]=true;
    }
    a.resize(n+5);
    for(i=1;i<n;i++)
    {
        ll u,v;
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    l=0;r=n;
    dfs1(1,1);
    while(l<=r)
    {
        mid=(l+r)/2;dem=0;
        dfs2();
        if(mx[1]>=0) dem++;
        if(dem<=m) {res=min(res,mid);r=mid-1;}
        else l=mid+1;
    }
    cout<<res;
    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