Submission #1104374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104374		overwatch9	Paprike (COI18_paprike)	C++17	100 / 100	82 ms	19056 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
int n, k;
vector <vector <int>> adj;
vector <int> vals;
int ans;
int dfs(int s, int p) {
    int x = vals[s];
    vector <int> tp;
    for (auto i : adj[s]) {
        if (i == p)
            continue;
        tp.push_back(dfs(i, s));
    }
    sort(tp.begin(), tp.end());
    for (int i = 0; i < (int)tp.size(); i++) {
        if (tp[i] + x <= k)
            x += tp[i];
        else
            ans++;
    }
    return x;
}
int main() {
    cin >> n >> k;
    adj.resize(n+1);
    vals.resize(n+1);
    for (int i = 1; i <= n; i++)
        cin >> vals[i];
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        if ((int)adj[i].size() == 1) {
            dfs(i, i);
            break;
        }
    }
    cout << ans << '\n';
}

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