oj.uz

Submission #978735

# Submission time Handle Problem Language Result Execution time Memory
978735 2024-05-09T14:56:08 Z duckindog Chase (CEOI17_chase) C++17
100 / 100
 299 ms 170308 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 100'000 + 10,
          B = 100 + 10;
int n, b;
int a[N];
vector<int> ad[N];

struct sortedArry { 
  pair<long long, int> arr[3];
  void add(pair<long long, int> value) { 
    arr[2] = value;
    sort(arr, arr + 3, greater<>());
  }
};

long long answer;
long long dp1[N][B], dp2[N][B];
void dfs(int u, int p = 0) { 
  long long total = 0;
  for (const auto& v : ad[u]) {
    total += a[v];
    if (v == p) continue;
    dfs(v, u);
  }

  dp2[u][1] = total;
  vector<sortedArry> best(b + 1);
  best[1].add({total, 0});
  for (const auto& v : ad[u]) { 
    if (v == p) continue;
    for (int i = 1; i <= b; ++i) { 
      auto&ret = dp1[u][i];
      ret = max({ret, dp1[v][i], dp1[v][i - 1] + total - a[p]});
    }
    for (int i = 1; i <= b; ++i) { 
      auto& ret = dp2[u][i];
      long long val = max(dp2[v][i], dp2[v][i - 1] + total - a[v]);
      ret = max({ret, val});
      best[i].add({val, v});
    }
  }
  
  for (const auto& v : ad[u]) { 
    if (v == p) continue;
    for (int i = 1; i <= b; ++i) { 
      for (int j = 0; j < 2; ++j) { 
        const auto& [value, x] = best[i].arr[j];
        if (x == v) continue;
        answer = max(answer, value + dp1[v][b - i]);
      }
    }
  }
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> b;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 2; i <= n; ++i) {
    int u, v; cin >> u >> v;
    ad[u].push_back(v);
    ad[v].push_back(u);
  }
  
  dfs(1);

  cout << answer << "\n";
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 3 ms 7140 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 4 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 145956 KB Output is correct
2 Correct 254 ms 145884 KB Output is correct
3 Correct 205 ms 95684 KB Output is correct
4 Correct 109 ms 165716 KB Output is correct
5 Correct 275 ms 168020 KB Output is correct
6 Correct 273 ms 168020 KB Output is correct
7 Correct 293 ms 167960 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 3 ms 7140 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 4 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 265 ms 145956 KB Output is correct
14 Correct 254 ms 145884 KB Output is correct
15 Correct 205 ms 95684 KB Output is correct
16 Correct 109 ms 165716 KB Output is correct
17 Correct 275 ms 168020 KB Output is correct
18 Correct 273 ms 168020 KB Output is correct
19 Correct 293 ms 167960 KB Output is correct
20 Correct 291 ms 170308 KB Output is correct
21 Correct 56 ms 97364 KB Output is correct
22 Correct 275 ms 169808 KB Output is correct
23 Correct 104 ms 167760 KB Output is correct
24 Correct 299 ms 170104 KB Output is correct
25 Correct 193 ms 97476 KB Output is correct
26 Correct 233 ms 148052 KB Output is correct
27 Correct 244 ms 148180 KB Output is correct