oj.uz

Submission #583049

# Submission time Handle Problem Language Result Execution time Memory
583049 2022-06-24T17:56:23 Z 600Mihnea Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 91892 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];

void compute(int a, int p) {
  for (int i = 0; i <= bread_have; i++) {
    dp[a][i] = 0;
  }
  gain[a] = 0;
  for (auto &b : g[a]) {
    if (b != p) {
      gain[a] += pigs[b];
      for (int i = 1; i <= bread_have; i++) {
        dp[a][i] = max(dp[a][i], dp[b][i]);
      }
    }
  }
  for (int i = bread_have - 1; i >= 0; i--) {
    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 b) {
 /// swap(a, b);
  dfs(a, b);
  dfs(b, 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 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 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 3 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 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 747 ms 3596 KB Output is correct
8 Correct 109 ms 3604 KB Output is correct
9 Correct 81 ms 3540 KB Output is correct
10 Correct 800 ms 3548 KB Output is correct
11 Correct 293 ms 3540 KB Output is correct
12 Correct 192 ms 3540 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4062 ms 91892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
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 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 747 ms 3596 KB Output is correct
8 Correct 109 ms 3604 KB Output is correct
9 Correct 81 ms 3540 KB Output is correct
10 Correct 800 ms 3548 KB Output is correct
11 Correct 293 ms 3540 KB Output is correct
12 Correct 192 ms 3540 KB Output is correct
13 Execution timed out 4062 ms 91892 KB Time limit exceeded
14 Halted 0 ms 0 KB -