Submission #321973

#	Time	Username	Problem	Language	Result	Execution time	Memory
321973		ThaiBaHung	Paprike (COI18_paprike)	C++14	100 / 100	82 ms	21996 KiB

paprike

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;
int n, k;
int a[N];
typedef pair < int, int > ii;
vector < int > adj[N];
int dp[N];
vector < int > con[N];
int res = 0;

void dfs(int i, int j)
{
    bool IsLeaf = true;

    for (int u : adj[i])
    {
        if (u == j) continue;
        IsLeaf = false;
        dfs(u, i);

        con[i].push_back(dp[u]);
    }

    if (IsLeaf)
    {
        dp[i] = a[i];
        return;
    }

    sort(con[i].begin(), con[i].end());

    int sum = 0;

    for (int j = 0; j < con[i].size(); j++)
    {
        sum += con[i][j];

        if (a[i] + sum > k)
        {
            sum -= con[i][j];
            dp[i] = sum + a[i];

            res += con[i].size() - j;
            return;
        }
    }

    dp[i] = sum + a[i];
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("t.inp","r",stdin); freopen("t.out","w",stdout);

    cin >> n >> k;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, 0);

    cout << res;
}

Compilation message (stderr)

paprike.cpp: In function 'void dfs(int, int)':
paprike.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int j = 0; j < con[i].size(); j++)
      |                     ~~^~~~~~~~~~~~~~~

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