oj.uz

Submission #978731

# Submission time Handle Problem Language Result Execution time Memory
978731 2024-05-09T14:45:36 Z duckindog Chase (CEOI17_chase) C++17
30 / 100
 559 ms 338796 KB 
#include <bits/stdc++.h>

using namespace std;

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];

  dp2[u][1] = total;
  vector<sortedArry> best(b + 1);
  best[1].add({total, 0});
  for (const auto& v : ad[u]) { 
    if (v == p) continue;
    dfs(v, u);

    for (int i = 1; i <= b; ++i) { 
      auto&ret = dp1[u][i];
      long long val = max(dp1[v][i], dp1[v][i - 1] + total - a[p]);
      ret = max({ret, val});
    }
    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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Runtime error 7 ms 8796 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Runtime error 7 ms 8796 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 559 ms 338796 KB Output is correct
2 Correct 513 ms 337540 KB Output is correct
3 Correct 179 ms 96712 KB Output is correct
4 Correct 92 ms 166996 KB Output is correct
5 Correct 249 ms 169520 KB Output is correct
6 Correct 256 ms 169648 KB Output is correct
7 Correct 247 ms 169132 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Runtime error 7 ms 8796 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -