Submission #343552

#	Time	Username	Problem	Language	Result	Execution time	Memory
343552		parsabahrami	Paprike (COI18_paprike)	C++17	100 / 100	111 ms	19180 KiB

paprike

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

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 1e5 + 10, MOD = 1e9 + 7;
int n, k, A[N], res; vector<int> adj[N];

ll DFS(int v, int p = -1) {
    vector<ll> vec;
    for (int u : adj[v]) {
        if (u != p) vec.push_back(DFS(u, v));
    }
    sort(vec.begin(), vec.end());
    ll tot = A[v];
    for (ll x : vec) {
        if (tot + x <= k) tot += x;
        else res++;
    }
    return tot;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
    for (int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
    DFS(1);
    printf("%d\n", res);
    return 0;
}

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
paprike.cpp:31:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |     for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
      |                                  ~~~~~^~~~~~~~~~~~~
paprike.cpp:33:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |         int u, v; scanf("%d%d", &u, &v);
      |                   ~~~~~^~~~~~~~~~~~~~~~

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