| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 468634 |
2021-08-29T06:48:06 Z |
idk321 |
Chase (CEOI17_chase) |
C++17 |
|
246 ms |
524292 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
const int V = 101;
int p[N];
int n, v;
vector<int> adj[N];
struct comp {
bool operator () (const array<ll,2>& ar1, const array<ll,2>& ar2) const {
return ar1 > ar2;
}
};
bool comp_fn (const array<ll,2>& ar1, const array<ll,2>& ar2) {
return ar1 > ar2;
}
struct SetLike {
array<array<ll, 2>, 2> v;
int len = 0;
array<array<ll, 2>, 2>::iterator begin() {
return v.begin();
}
array<array<ll, 2>, 2>::iterator end() {
return v.begin() + len;
}
array<array<ll, 2>, 2>::iterator erase(array<array<ll, 2>, 2>::iterator it) {
len--;
if (it == v.begin()) {
swap(v[0], v[1]);
return v.begin();
}
return v.begin() + 1;
}
void insert(array<ll, 2> ar) {
if (len < 2) {
v[len] = ar;
len++;
} else {
if (ar > v[1]) swap(ar, v[1]);
if (v[1] > v[0]) swap(v[0], v[1]);
}
}
};
SetLike dp[N][2][V];
void dfs(int node, int par) {
ll val1 = 0;
for (int next : adj[node]) {
if (next == par) continue;
val1 += p[next];
dfs(next, node);
}
dp[node][1][1].insert({val1, node});
for (int next : adj[node]) {
if (next == par) continue;
for (int i = 0; i <= v; i++) {
dp[node][0][i].insert({max((*dp[next][0][i].begin())[0], (*dp[next][1][i].begin())[0]), next});
if (i != v) dp[node][1][i + 1].insert({max(val1 + (*dp[next][0][i].begin())[0], val1 + (*dp[next][1][i].begin())[0]), next});
}
}
for (int i = 0; i <= v; i++) {
for (int j = 0; j < 2; j++) dp[node][j][i].insert({0, node});
}
}
void transferRoot(int first, int second) {
ll defaultValue = 0;
for (int next : adj[second]) {
if (next == first) continue;
defaultValue += p[next];
}
for (int i = 0; i <= v; i++) {
auto it0 = dp[first][0][i].begin();
auto it1 = dp[first][1][i].begin();
if ((*it0)[1] == second) it0++;
if ((*it1)[1] == second) it1++;
ll val0 = 0;
ll val1 = 0;
if (it0 != dp[first][0][i].end()) val0 = (*it0)[0];
if (it1 != dp[first][1][i].end()) val1 = (*it1)[0];
dp[second][0][i].insert({max(val0, val1 - p[second]), first});
if (i != v) dp[second][1][i + 1].insert({max(val0 + defaultValue, val1 - p[second] + defaultValue), first});
}
for (int i = 1; i <= v; i++) {
auto it = dp[second][1][i].begin();
array<ll, 2> newEl = {(*it)[0] + p[first], (*it)[1]};
it = dp[second][1][i].erase(it);
if (it != dp[second][1][i].end()) {
array<ll, 2> newEl2 = {(*it)[0] + p[first], (*it)[1]};
dp[second][1][i].erase(it);
dp[second][1][i].insert(newEl2);
}
dp[second][1][i].insert(newEl);
}
}
ll result = 0;
void dfsRoot(int node, int par) {
for (int i = 0; i <= v; i++) {
for (int j = 0; j < 2; j++) {
result = max(result, (*dp[node][j][i].begin())[0]);
}
}
cout << node << " " << result << endl;
for (int next : adj[node]) {
if (next == par) continue;
transferRoot(node, next);
dfsRoot(next, node);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> v;
for (int i = 1; i <= n; i++) cin >> p[i];
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1, -1);
dfsRoot(1, -1);
cout << result << "\n";
}
/*
12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
246 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
246 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
240 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
246 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
