Submission #1117597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117597		vjudge1	Paprike (COI18_paprike)	C++17	100 / 100	41 ms	18172 KiB

paprike

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

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

    vector<ll> dp(N, 0);
    auto cmp = [&](int x, int y) {
        return dp[x] > dp[y];
    };
    int ans = 0;
    function<void(int, int)> dfs = [&](int si, int pi) {
        dp[si] = arr[si];
        for (auto v : g[si]) if (v != pi) {
            dfs (v, si);
            dp[si] += dp[v];
        }
        sort (g[si].begin(), g[si].end(), cmp);
        for (int i = 0;i < g[si].size();i ++) if (dp[si] > K && g[si][i] != pi) {
            dp[si] -= dp[g[si][i]];
            ans ++;
        }
    };
    dfs (0, 0);
    cout << ans << "\n";
}

Compilation message (stderr)

paprike.cpp: In lambda function:
paprike.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int i = 0;i < g[si].size();i ++) if (dp[si] > K && g[si][i] != pi) {
      |                        ~~^~~~~~~~~~~~~~

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