Submission #648955

#	Time	Username	Problem	Language	Result	Execution time	Memory
648955		vladutpiele	Paprike (COI18_paprike)	C++17	100 / 100	59 ms	22648 KiB

paprike

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int nmax = 100000;

int n, k;
int v[nmax + 5];
struct elem
{
    int minCuts;
    int minSum;
};
elem dp[nmax + 5];
vector<int> g[nmax + 5];

void dfs(int fiu, int tata)
{
    priority_queue<int> coada;
    dp[fiu].minCuts = 0;
    dp[fiu].minSum = v[fiu];
    for(auto it : g[fiu])
    {
        if(it == tata)
        {
            continue;
        }
        dfs(it, fiu);
        dp[fiu].minCuts += dp[it].minCuts;
        dp[fiu].minSum += dp[it].minSum;
        coada.push(dp[it].minSum);
    }
    while(dp[fiu].minSum > k)
    {
        dp[fiu].minCuts ++;
        dp[fiu].minSum -= coada.top();
        coada.pop();
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)
    {
        cin >> v[i];
    }
    for(int i = 1; i < n; i ++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    cout << dp[1].minCuts << '\n';
    return 0;
}

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