Submission #1294103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294103		dragonrobot	Paprike (COI18_paprike)	C++20	13 / 100	75 ms	11300 KiB

paprike

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

vector<vector<int>> adj;
vector<long long> h;
long long k;
int total_cuts = 0;

long long dfs(int u, int p) {
    long long current_wreath_spiciness = h[u];
    for (int v : adj[u]) {
        if (v == p) continue;
        long long spiciness_from_child = dfs(v, u);
        if (current_wreath_spiciness + spiciness_from_child <= k) current_wreath_spiciness += spiciness_from_child;
        else total_cuts++;
    }
    return current_wreath_spiciness;
}

int main() {
    int n;
    cin >> n >> k;
    h.resize(n + 1);
    adj.resize(n + 1);
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    cout << total_cuts << endl;
    return 0;
}

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