Submission #44612

#TimeUsernameProblemLanguageResultExecution timeMemory
44612ulnaPaprike (COI18_paprike)C++11
0 / 100
77 ms18916 KiB
#include <bits/stdc++.h> using namespace std; // why am I so weak int n; long long k; int a[100055]; int cut[100055]; long long dp[100055]; int pt[100055]; vector<int> g[100055]; typedef pair<long long, int> P; #define ft first #define sd second void dfs(int v, int par = -1) { dp[v] = a[v]; for (auto u : g[v]) if (u != par) { dfs(u, v); dp[v] += dp[u]; cut[v] += cut[u]; } sort(g[v].begin(), g[v].end(), [&] (int u, int v) { return dp[u] > dp[v]; }); pt[v] = 0; for (int i = 0; i < (int)g[v].size(); i++) { int u = g[v][i]; if (u == par) continue; if (dp[v] <= k) { pt[v] = i; break; } cut[v]++; dp[v] -= dp[u]; } } int res = INT_MAX; void rdfs(int v, int par = -1, P ac = P(0, 0)) { int temp = 0; dp[v] += ac.ft; bool diu = false; while (dp[v] > k) { if (pt[v] >= (int)g[v].size()) { dp[v] -= ac.ft; temp++; continue; } int u = g[v][pt[v]]; if (!diu && ac.ft >= dp[u]) { diu = true; dp[v] -= ac.ft; temp++; continue; } pt[v]++; if (u == par) continue; temp++; dp[v] -= dp[u]; } res = min(res, ac.sd + temp + cut[v]); for (int i = (int)g[v].size() - 1; i >= 0; i--) { int u = g[v][i]; if (u == par) continue; if (i < pt[i]) { rdfs(u, v, P(dp[v], ac.sd + temp + cut[v] - 1)); } else { long long cur = dp[v] - dp[u]; int spe = 0; bool shit = false; for (int j = pt[v] - 1; j >= 0; j--) { int u = g[v][j]; if (u == par) continue; if (!shit && diu && cur + ac.ft <= k && ac.ft <= dp[u]) { cur += ac.ft; spe++; shit = true; } if (cur + dp[u] > k) break; cur += dp[u]; spe++; } if (diu && cur + ac.ft <= k && !shit) { cur += ac.ft; spe++; } rdfs(u, v, P(cur, ac.sd + temp + cut[v] - spe)); } } } 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); } dfs(0); rdfs(0); printf("%d\n", res); return 0; }

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:124: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:128: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...