제출 #1025644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1025644		AtinaR	Paprike (COI18_paprike)	C++14	100 / 100	34 ms	18428 KiB

paprike

#include <bits/stdc++.h>

using namespace std;
const long long MAX=1e5+10;
long long n,k;
long long niza[MAX];
bool vis[MAX];
long long sumofsub[MAX];
vector<long long> graph[MAX];
long long res=0;
void dfs(long long node, long long parent)
{
    sumofsub[node]=niza[node];
    vector<long long> v;
    for(auto x:graph[node])
    {
        if(x==parent)continue;
        dfs(x,node);
        v.push_back(sumofsub[x]);
        sumofsub[node]+=sumofsub[x];
    }
    if(sumofsub[node]>k)
    {
        sort(v.begin(),v.end());
        long long zbir=niza[node];
        for(auto x:v)
        {
            if(zbir+x>k)
            {
                sumofsub[node]-=x;
                res++;
            }
            else zbir+=x;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>k;
    for(long long i=0; i<n; i++)cin>>niza[i];
    for(long long i=0; i<n-1; i++)
    {
        long long a,b;
        cin>>a>>b;
        a--;b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs(0,0);
    cout<<res<<endl;
    return 0;
}

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