oj.uz

Submission #583299

# Submission time Handle Problem Language Result Execution time Memory
583299 2022-06-25T08:20:52 Z 600Mihnea Chase (CEOI17_chase) C++17
100 / 100
 494 ms 235916 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];
vector<int> g[N];
ll sum_vecs[N];
ll dp1[N][B];
ll dp2[N][B];
ll dp3[N][B];
ll big[B];
ll sol;

void dfs1(int a, int p = 0) {
  for (auto &b : g[a]) {
    if (b != p) {
      dfs1(b, a);
    }
  }
  for (int i = 0; i <= bread_have; i++) {
    if (i >= 1) {
      dp1[a][i] = max(dp1[a][i], sum_vecs[a]);
    }
  }
  for (auto &b : g[a]) {
    if (b == p) {
      continue;
    }
    for (int i = 0; i <= bread_have; i++) {
      dp1[a][i] = max(dp1[a][i], dp1[b][i]);
      if (i >= 1) {
        dp1[a][i] = max(dp1[a][i], dp1[b][i - 1] + (sum_vecs[a] - pigs[b]));
      }
    }
  }
}

void dfs2(int a, int p = 0) {
  for (auto &b : g[a]) {
    if (b != p) {
      dfs2(b, a);
    }
  }
  for (auto &b : g[a]) {
    if (b == p) {
      continue;
    }
    for (int i = 0; i <= bread_have; i++) {
      dp2[a][i] = max(dp2[a][i], dp2[b][i]);
      if (i >= 1) {
        dp2[a][i] = max(dp2[a][i], dp2[b][i - 1] + (sum_vecs[a] - pigs[p]));
      }
    }
  }
  for (auto &b : g[a]) {
    if (b == p) {
      continue;
    }
    for (int i = 0; i <= bread_have; i++) {
      dp3[a][i] = max(dp3[a][i], dp2[b][i]);
      if (i >= 1) {
        dp3[a][i] = max(dp3[a][i], dp2[b][i - 1] + sum_vecs[a]);
      }
    }
  }
}


void dfs3(int a, int p = 0) {
  vector<int> Kids;
  for (auto &b : g[a]) {
    if (b != p) {
      dfs3(b, a);
      Kids.push_back(b);
    }
  }
  g[a] = Kids;
  sol = max(sol, sum_vecs[a]);
  sol = max(sol, dp1[a][bread_have]);
  sol = max(sol, dp2[a][bread_have]);
  sol = max(sol, dp3[a][bread_have]);


  for (int iter = 0; iter < 2; iter++) {
    for (int i = 0; i <= bread_have; i++) {
      big[i] = -INF;
    }
    for (auto &b : Kids) {
      for (int i = 0; i <= bread_have; i++) {
        sol = max(sol, dp1[b][i] + big[bread_have - i]);
      }
      for (int i = 0; i + 1 <= bread_have; i++) {
        sol = max(sol, dp1[b][i] + big[bread_have - i - 1] + (sum_vecs[a] - pigs[b]));
      }
      for (int i = 0; i <= bread_have; i++) {
        big[i] = max(big[i], dp2[b][i]);
      }
    }
    reverse(Kids.begin(), Kids.end());
  }
}

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

  cin >> n >> bread_have;

  for (int i = 1; i <= n; i++) {
    cin >> pigs[i];
  }

  for (int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
    sum_vecs[a] += pigs[b];
    sum_vecs[b] += pigs[a];
  }
  if (bread_have == 0) {
    cout << "0\n";
    return 0;
  }
  dfs1(1);
  dfs2(1);
  dfs3(1);
  cout << sol << "\n";

}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 5 ms 4436 KB Output is correct
8 Correct 3 ms 4436 KB Output is correct
9 Correct 3 ms 3540 KB Output is correct
10 Correct 5 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 180816 KB Output is correct
2 Correct 392 ms 180936 KB Output is correct
3 Correct 258 ms 92136 KB Output is correct
4 Correct 242 ms 230984 KB Output is correct
5 Correct 494 ms 235736 KB Output is correct
6 Correct 478 ms 235652 KB Output is correct
7 Correct 439 ms 235452 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 5 ms 4436 KB Output is correct
8 Correct 3 ms 4436 KB Output is correct
9 Correct 3 ms 3540 KB Output is correct
10 Correct 5 ms 4948 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 371 ms 180816 KB Output is correct
14 Correct 392 ms 180936 KB Output is correct
15 Correct 258 ms 92136 KB Output is correct
16 Correct 242 ms 230984 KB Output is correct
17 Correct 494 ms 235736 KB Output is correct
18 Correct 478 ms 235652 KB Output is correct
19 Correct 439 ms 235452 KB Output is correct
20 Correct 460 ms 235916 KB Output is correct
21 Correct 50 ms 9168 KB Output is correct
22 Correct 443 ms 235228 KB Output is correct
23 Correct 258 ms 231380 KB Output is correct
24 Correct 442 ms 235636 KB Output is correct
25 Correct 241 ms 93800 KB Output is correct
26 Correct 378 ms 183148 KB Output is correct
27 Correct 360 ms 183112 KB Output is correct