Submission #1117591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117591		vjudge1	Paprike (COI18_paprike)	C++17	100 / 100	60 ms	84820 KiB

paprike

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

const int MXN = 3e6 + 5;
const int mod = 998244353;

int n, k;
vector<int> adj[MXN];
int val[MXN];
int res = 0;

void dfs(int a, int p)
{
  vector<int> vx;
  for (int &v : adj[a])
  {
    if (v == p) continue;
    dfs(v, a);
    vx.push_back(val[v]);
  }
  sort(vx.begin(), vx.end());
  for (int i = 0; i < vx.size(); i++)
  {
    if (val[a] + vx[i] <= k) val[a] += vx[i];
    else res++;
  }
}

void _()
{
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> val[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, 1);
  cout << res << '\n';
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) _();
}

Compilation message (stderr)

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

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