Submission #850948

#	Time	Username	Problem	Language	Result	Execution time	Memory
850948		Cyanmond	Paprike (COI18_paprike)	C++17	100 / 100	39 ms	21072 KiB

paprike

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= l; --i)
#define ALL(x) (x).begin(), (x).end()

using i64 = long long;

void main_() {
    int N;
    i64 K;
    cin >> N >> K;
    vector<i64> H(N);
    for (auto &e : H) cin >> e;
    vector<vector<int>> Tree(N);
    rep(i, 0, N - 1) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        Tree[a].push_back(b);
        Tree[b].push_back(a);
    }

    int ans = 0;
    auto dfs = [&](auto &&self, const int v, const int p) -> i64 {
        vector<i64> res;
        for (const auto t : Tree[v]) {
            if (t == p) continue;
            res.push_back(self(self, t, v));
        }
        sort(ALL(res));
        bool isOk = true;
        i64 s = 0;
        for (const auto e : res) {
            if (isOk and s + e + H[v] <= K) {
                s += e;
            } else {
                isOk = false;
                ++ans;
            }
        }
        return s + H[v];
    };
    dfs(dfs, 0, -1);

    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    main_();
}

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