Submission #533065

#	Time	Username	Problem	Language	Result	Execution time	Memory
533065		alextodoran	Paprike (COI18_paprike)	C++17	100 / 100	66 ms	19852 KiB

paprike

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;

int N, K;
int w[N_MAX + 2];
vector <int> adj[N_MAX + 2];

int minCuts[N_MAX + 2];
int minSum[N_MAX + 2];

void dfs (int u, int par = -1) {
    minCuts[u] = 0;
    minSum[u] = w[u];
    vector <int> sums;
    for (int v : adj[u]) {
        if (v != par) {
            dfs(v, u);
            minCuts[u] += minCuts[v];
            sums.push_back(minSum[v]);
        }
    }
    sort(sums.begin(), sums.end(), greater <int> ());
    while (sums.empty() == false && minSum[u] + sums.back() <= K) {
        minSum[u] += sums.back();
        sums.pop_back();
    }
    minCuts[u] += (int) sums.size();
}

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

    cin >> N >> K;
    for (int u = 1; u <= N; u++) {
        cin >> w[u];
    }
    for (int i = 1; i <= N - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1);

    cout << minCuts[1] << "\n";

    return 0;
}

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