Submission #930524

#	Time	Username	Problem	Language	Result	Execution time	Memory
930524		sleepntsheep	Paprike (COI18_paprike)	C++17	100 / 100	37 ms	18016 KiB

paprike

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#define N 100003

int n, K, a[N];
std::basic_string<int> g[N];

int dp[N];
long long b[N];

void dfs(int u, int p)
{
    b[u] += a[u];

    std::vector<long long> bot;

    for (int v : g[u]) if ( v - p )
    {
        dfs(v, u);
        bot.push_back(b[v]);
        dp[u] += dp[v];
        b[u] += b[v];
    }
    std::sort(bot.begin(), bot.end());

    while (b[u] > K)
    {
        b[u] -= bot.back();
        ++dp[u];
        bot.pop_back();
    }
}

int main()
{
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; ++i) scanf("%d", a+i);
    for (int u, v, i = 1; i < n; ++i) scanf("%d%d", &u, &v), g[u].push_back(v), g[v].push_back(u);
    dfs(1, 1);
    printf("%d", dp[1]);
    return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d%d", &n, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~
paprike.cpp:39:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     for (int i = 1; i <= n; ++i) scanf("%d", a+i);
      |                                  ~~~~~^~~~~~~~~~~
paprike.cpp:40:44: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     for (int u, v, i = 1; i < n; ++i) scanf("%d%d", &u, &v), g[u].push_back(v), g[v].push_back(u);
      |                                       ~~~~~^~~~~~~~~~~~~~~~

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