oj.uz

Submission #583262

# Submission time Handle Problem Language Result Execution time Memory
583262 2022-06-25T07:11:47 Z 600Mihnea Chase (CEOI17_chase) C++17
40 / 100
 1312 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = (int) 1e5 + 7;
const int B = 100 + 7;
const ll INF = (ll) 1e18 + 7;
int n, bread_have, pigs[N];
ll gain[N];
ll dp[N][B];
ll sol = -INF;
vector<int> g[N];
multiset<ll> s[N][B];

void compute(int a, int p) {
  for (int i = 0; i <= bread_have; i++) {
    s[a][i].clear();
    s[a][i].insert(0);
  }
  gain[a] = 0;
  for (auto &b : g[a]) {
    if (b != p) {
      gain[a] += pigs[b];
      for (int i = 1; i <= bread_have; i++) {
        s[a][i].insert(-dp[b][i]);
      }
    }
  }
  for (int i = bread_have; i >= 0; i--) {
    dp[a][i] = -*s[a][i].begin();
    if (i + 1 <= bread_have) {
      dp[a][i + 1] = max(dp[a][i + 1], dp[a][i] + gain[a]);
    }
  }
}



void dfs(int a, int p = 0) {
  for (auto &b : g[a]) {
    if (b != p) {
      dfs(b, a);
    }
  }

  compute(a, p);
}

void reroot(int a, int p) {
  compute(a, p);
  compute(p, 0);
}

void solve(int a, int p = 0) {
  sol = max(sol, dp[a][bread_have]);
  for (auto &b : g[a]) {
    if (b != p) {
      reroot(a, b);
      solve(b, a);
      reroot(b, a);
    }
  }
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

///  freopen ("input.txt", "r", stdin);

  cin >> n >> bread_have;
  for (int i = 1; i <= n; i++) {
    cin >> pigs[i];
    for (int j = 1; j <= bread_have; j++) {
      s[i][j].insert(0);
    }
  }

  for (int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs(1);
  solve(1);
  cout << sol << "\n";
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 505256 KB Output is correct
2 Correct 257 ms 505152 KB Output is correct
3 Correct 251 ms 505248 KB Output is correct
4 Correct 285 ms 505364 KB Output is correct
5 Correct 256 ms 505272 KB Output is correct
6 Correct 279 ms 505240 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 505256 KB Output is correct
2 Correct 257 ms 505152 KB Output is correct
3 Correct 251 ms 505248 KB Output is correct
4 Correct 285 ms 505364 KB Output is correct
5 Correct 256 ms 505272 KB Output is correct
6 Correct 279 ms 505240 KB Output is correct
7 Correct 325 ms 515600 KB Output is correct
8 Correct 283 ms 506596 KB Output is correct
9 Correct 1312 ms 506664 KB Output is correct
10 Correct 327 ms 515620 KB Output is correct
11 Correct 285 ms 508948 KB Output is correct
12 Correct 299 ms 507036 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 225 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 505256 KB Output is correct
2 Correct 257 ms 505152 KB Output is correct
3 Correct 251 ms 505248 KB Output is correct
4 Correct 285 ms 505364 KB Output is correct
5 Correct 256 ms 505272 KB Output is correct
6 Correct 279 ms 505240 KB Output is correct
7 Correct 325 ms 515600 KB Output is correct
8 Correct 283 ms 506596 KB Output is correct
9 Correct 1312 ms 506664 KB Output is correct
10 Correct 327 ms 515620 KB Output is correct
11 Correct 285 ms 508948 KB Output is correct
12 Correct 299 ms 507036 KB Output is correct
13 Runtime error 225 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -