oj.uz

Submission #583298

# Submission time Handle Problem Language Result Execution time Memory
583298 2022-06-25T08:19:08 Z 600Mihnea Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 181728 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 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 (auto &b : Kids) {
    for (auto &c : Kids) {
      if (b == c) {
        continue;
      }
      for (int i = 0; i <= bread_have; i++) {
        sol = max(sol, dp1[b][i] + dp2[c][bread_have - i]);
      }
      for (int i = 0; i + 1 <= bread_have; i++) {
        sol = max(sol, dp1[b][i] + dp2[c][bread_have - i - 1] + (sum_vecs[a] - pigs[b]));
      }
    }
  }
}

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 2 ms 2644 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 181728 KB Output is correct
2 Correct 386 ms 181648 KB Output is correct
3 Execution timed out 4085 ms 92168 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 5 ms 4508 KB Output is correct
8 Correct 4 ms 4488 KB Output is correct
9 Correct 19 ms 3540 KB Output is correct
10 Correct 5 ms 5008 KB Output is correct
11 Correct 4 ms 4948 KB Output is correct
12 Correct 6 ms 4948 KB Output is correct
13 Correct 407 ms 181728 KB Output is correct
14 Correct 386 ms 181648 KB Output is correct
15 Execution timed out 4085 ms 92168 KB Time limit exceeded
16 Halted 0 ms 0 KB -