제출 #645605

#제출 시각아이디문제언어결과실행 시간메모리
645605tth37Chase (CEOI17_chase)C++14
0 / 100
297 ms260160 KiB
#include <iostream> #include <vector> const int N = 1e5 + 5; const int M = 100 + 5; const long long INF = 1e18; using pll = std::pair<long long, long long>; int n, m; std::vector<int> G[N]; long long a[N], sum[N], f[N][M], sum_u, f_u[M], ans = -INF; pll mx[N][M], mx_u[M]; void update_mx(pll &cur, long long val) { if (val > cur.first) { cur.second = cur.first; cur.first = val; } else if (val > cur.second) { cur.second = val; } } void remove_mx(pll &cur, long long val) { if (cur.first == val) { cur.first = cur.second; cur.second = -INF; } else if (cur.second == val) { cur.second = -INF; } } void dfs1(int u, int fa) { for (int i = 1; i <= m; ++i) mx[u][i] = {-INF, -INF}; for (auto v : G[u]) { if (v == fa) continue; dfs1(v, u); sum[u] += a[v]; for (int i = 1; i <= m; ++i) { update_mx(mx[u][i], -a[v] + f[v][i - 1]); } } f[u][0] = a[u] + sum[u]; for (int i = 1; i <= m; ++i) { f[u][i] = a[u] + sum[u] + mx[u][i].first; } } void dfs2(int u, int fa) { for (auto v : G[u]) { if (v == fa) continue; // h'[u] sum_u = sum[u] - a[v]; for (int i = 1; i <= m; ++i) { mx_u[i] = mx[u][i]; remove_mx(mx_u[i], -a[v] + f[v][i - 1]); } // f'[u] f_u[0] = a[u] + sum_u; for (int i = 1; i <= m; ++i) { f_u[i] = a[u] + sum_u + mx_u[i].first; } // h[v] sum[v] += a[u]; for (int i = 1; i <= m; ++i) { update_mx(mx[v][i], -a[u] + f_u[i - 1]); } // f[v] f[v][0] = a[v] + sum[v]; for (int i = 1; i <= m; ++i) { f[v][i] = a[v] + sum[v] + mx[v][i].first; } dfs2(v, u); } } int main() { scanf("%d%d", &n, &m); if (m == 0) { puts("0"); return 0; } for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]); for (int i = 1; i < n; ++i) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v), G[v].push_back(u); } dfs1(1, 0); dfs2(1, 0); for (int u = 1; u <= n; ++u) { long long cur = -INF; for (int i = 0; i <= m - 1; ++i) cur = std::max(cur, f[u][i]); ans = std::max(ans, cur - a[u]); } // for (int i = 1; i <= n; ++i) // std::cout << f[i][0] << " "; printf("%lld", ans); return 0; } /* 12 2 2 3 3 8 1 5 6 7 8 3 5 4 2 1 2 7 3 4 4 7 7 6 5 6 6 8 6 9 7 10 10 11 10 12 */

컴파일 시 표준 에러 (stderr) 메시지

chase.cpp: In function 'int main()':
chase.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
chase.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     scanf("%lld", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~~~
chase.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     scanf("%d%d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...