oj.uz

답안 #583049

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4062 ms 91892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 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 -