Submission #311633

#TimeUsernameProblemLanguageResultExecution timeMemory
311633biggChase (CEOI17_chase)C++14
100 / 100
323 ms273400 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e5 + 10; const int MAXK = 110; ll dp1[MAXN][MAXK], dp2[MAXN][MAXK]; ll s[MAXN], a[MAXN]; int crum; vector<int> grafo[MAXN]; ll ans; void dfs(int x, int p){ pair<ll, ll> maxi[MAXK]; for(int i = 0; i <= crum; i++){ maxi[i] = make_pair(0, 0); } dp1[x][0] = dp2[x][0] = 0; dp2[x][1] = s[x]; for(int i = 0; i < grafo[x].size(); i++){ int viz = grafo[x][i]; if(viz == p) continue; dfs(viz, x); for(int k = 1; k <= crum; k++){ dp1[x][k] = max(dp1[viz][k], dp1[x][k]); dp1[x][k] = max(dp1[x][k], dp1[viz][k-1] + s[x] - a[p]); dp2[x][k] = max(dp2[viz][k], dp2[x][k]); dp2[x][k] = max(dp2[x][k], dp2[viz][k-1] + s[x] - a[viz]); ll val = dp1[viz][k]; if(val >= maxi[k].first) swap(maxi[k].first, val); if(val >= maxi[k].second) swap(maxi[k].second, val); } } for(int i = 0; i < grafo[x].size(); i++){ int viz = grafo[x][i]; if(viz == p) continue; ans = max(ans, dp1[viz][crum-1] + s[x]); for(int k = 0; k <= crum; k++){ ll loc = max(dp2[viz][k], k ? dp2[viz][k-1] + s[x] - a[viz] : 0); if(dp1[viz][crum-k]!= maxi[crum-k].first) ans = max(ans, loc + maxi[crum - k].first); else ans = max(ans, loc + maxi[crum-k].second); } } } int n; int main(){ scanf("%d %d", &n, &crum); if(crum == 0){ printf("0\n" ); 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); grafo[u].push_back(v); grafo[v].push_back(u); s[u] += a[v]; s[v] += a[u]; } dfs(1, 0); printf("%lld\n",ans ); }

Compilation message (stderr)

chase.cpp: In function 'void dfs(int, int)':
chase.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i = 0; i < grafo[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~
chase.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i = 0; i < grafo[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~
chase.cpp: In function 'int main()':
chase.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  scanf("%d %d", &n, &crum);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
chase.cpp:54:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |  for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
      |                              ~~~~~^~~~~~~~~~~~~~~
chase.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |   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...