Submission #89973

#	Time	Username	Problem	Language	Result	Execution time	Memory
89973		vex	Paprike (COI18_paprike)	C++14	100 / 100	119 ms	47692 KiB

paprike

#include <bits/stdc++.h>
#define maxn 1000005
#define pii pair<int,int>
#define ljutina first
#define brojSecenja second
#define par second.second
#define node second.first
using namespace std;

int n,k;
int h[maxn];
vector<pair<pii,pii>>adj[maxn];
pii dp[maxn];

bool cmp(pair<pii,pii> ff,pair<pii,pii> ss)
{
    if(ff.par==1)return true;
    if(ss.par==1)return false;
    return ff.first.ljutina<ss.first.ljutina;
}

void dfs(int v,int p)
{
    dp[v].ljutina=0;
    dp[v].brojSecenja=0;
    bool leaf=true;

    for(auto x:adj[v])
    {
        int u=x.node;
        if(u==p)
        {
            x.par=1;
            continue;
        }
        dfs(u,v);
        leaf=false;
    }

    dp[v].ljutina=h[v];
    if(leaf)return;
    int len=adj[v].size();
    for(int i=0;i<len;i++)
    {
        int cv=adj[v][i].node;
        adj[v][i].first.ljutina=dp[cv].ljutina;
        adj[v][i].first.brojSecenja=dp[cv].brojSecenja;
    }

    sort(adj[v].begin(),adj[v].end(),cmp);
    /*cout<<v<<"   ";
    for(auto x:adj[v])
    {
        cout<<x.first.ljutina<<","<<x.first.brojSecenja<<","<<x.node<<","<<x.par<<" ";
    }cout<<endl;*/

    int poc=0;if(p!=v)poc=1;
    for(int i=poc;i<len;i++)
    {
        int cv=adj[v][i].node;
        dp[v].brojSecenja+=dp[cv].brojSecenja;
        if(dp[v].ljutina+dp[cv].ljutina<=k)dp[v].ljutina+=dp[cv].ljutina;
        else dp[v].brojSecenja++;
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>h[i];
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        adj[x].push_back({{0,0},{y,0}});
        adj[y].push_back({{0,0},{x,0}});
    }

    dfs(1,1);

    //for(int i=1;i<=n;i++)cout<<dp[i].ljutina<<","<<dp[i].brojSecenja<<"  ";
    cout<<dp[1].brojSecenja<<endl;
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 27 / 27
• Subtask 4: 49 / 49