Submission #505099

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
505099	2022-01-10T13:47:35 Z	tgbegimx	Dynamite (POI11_dyn)	C++14	100 / 100	695 ms	28308 KB

#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.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	332 KB	Output is correct
2	Correct	332 KB	Output is correct
3	Correct	204 KB	Output is correct
4	Correct	204 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	332 KB	Output is correct
2	Correct	332 KB	Output is correct
3	Correct	332 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	1100 KB	Output is correct
2	Correct	18 ms	2124 KB	Output is correct
3	Correct	19 ms	2508 KB	Output is correct
4	Correct	20 ms	3660 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	4180 KB	Output is correct
2	Correct	51 ms	5652 KB	Output is correct
3	Correct	100 ms	6096 KB	Output is correct
4	Correct	102 ms	7712 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	143 ms	7768 KB	Output is correct
2	Correct	116 ms	7852 KB	Output is correct
3	Correct	143 ms	7604 KB	Output is correct
4	Correct	158 ms	11128 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	390 ms	14972 KB	Output is correct
2	Correct	382 ms	17568 KB	Output is correct
3	Correct	539 ms	22780 KB	Output is correct
4	Correct	540 ms	22744 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	674 ms	23516 KB	Output is correct
2	Correct	549 ms	22716 KB	Output is correct
3	Correct	630 ms	25264 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	695 ms	27216 KB	Output is correct
2	Correct	527 ms	22952 KB	Output is correct
3	Correct	682 ms	28308 KB	Output is correct
4	Correct	291 ms	22964 KB	Output is correct

Submission #505099

Compilation message