(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

Submission #44615

#TimeUsernameProblemLanguageResultExecution timeMemory
44615ulnaPaprike (COI18_paprike)C++11
100 / 100
95 ms16744 KiB
#include <bits/stdc++.h> using namespace std; // why am I so weak int n, k; int a[100055]; long long dp[100055]; vector<int> g[100055]; int dfs(int v, int par = -1) { dp[v] = a[v]; int res = 0; for (auto u : g[v]) if (u != par) { res += dfs(u, v); dp[v] += dp[u]; } sort(g[v].begin(), g[v].end(), [&] (int u, int v) { return dp[u] > dp[v]; }); for (auto u : g[v]) if (u != par) { if (dp[v] <= k) break; res++; dp[v] -= dp[u]; } return res; } int main() { cin >> n >> k; for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i + 1 < n; i++) { int x, y; scanf("%d %d", &x, &y); x--, y--; g[x].push_back(y); g[y].push_back(x); } printf("%d\n", dfs(0)); return 0; }

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:37:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
                              ~~~~~^~~~~~~~~~~~~
paprike.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...