| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1111335 |
2024-11-12T06:24:12 Z |
Zero_OP |
Chase (CEOI17_chase) |
C++14 |
|
186 ms |
102728 KB |
#include <bits/stdc++.h>
using namespace std;
template<typename T>
bool maximize(T& a, const T& b){
if(a < b){
return a = b, true;
} return false;
}
const int MAX_N = 1e5 + 5;
const int MAX_K = 100 + 5;
int N, K, p[MAX_N];
long long sum_neighbor[MAX_N];
vector<int> adj[MAX_N];
long long f[MAX_N][MAX_K], g[MAX_N][MAX_K], ans;
//f[u][i] = if p[u] > 0
//g[u][i] = if p[u] = 0
void dfs(int u, int pre){
for(int v : adj[u]) if(v != pre){
dfs(v, u);
}
for(int v : adj[u]) if(v != pre){
for(int i = 1; i <= K; ++i){
maximize(f[u][i], max(f[v][i - 1] - (i == 1 ? 0 : p[v]), g[v][i - 1] - p[v]) + sum_neighbor[u]);
maximize(g[u][i], f[v][i]);
}
}
vector<long long> info_f(K + 1, 0);
vector<long long> info_g(K + 1, 0);
vector<long long> info_g_sub(K + 1, 0);
vector<long long> info_f_sub(K + 1, 0);
/*
Case 1 : drop breadcumb at u
if both empty : g[v1][i] + g[v2][j] + sum_neighbor[u] - p[v1] - p[v2]
if the previous is empty and the current is not empty : g[v1][i] + f[v2][j] + sum_neighbor[u] - p[v1]
if the previous is not empty, but the current is empty : f[v1][i] + g[v2][j] + sum_neghbor[u] - p[v2]
if both not empty : f[v1][i] + f[v2][j] + sum_neighbor[u]
Case 2 : not drop a breadcumb at u
if both empty : g[v1][i] + g[v2][j]
if the previous is empty and the current is not empty : g[v1][i] + f[v2][j]
if the previous is not empty, but the current is empty : f[v1][i] + g[v2][j]
if both not empty : f[v1][i] + g[v2][j]
*/
maximize(ans, max(f[u][K], g[u][K]));
bool exist_subtrees = false;
for(int v : adj[u]) if(v != pre){
if(exist_subtrees){
//drop breadcumb at u
for(int i = 0; i < K; ++i){
//both is empty
maximize(ans, info_g_sub[i] + g[v][K - i - 1] + sum_neighbor[u]);
//previous is empty, p[v] is still
maximize(ans, info_g_sub[i] + f[v][K - i - 1] + sum_neighbor[u] - p[v]);
//previous is not empty, but p[v] is empty
maximize(ans, info_f_sub[i] + g[v][K - i - 1] + sum_neighbor[u]);
//both not empty
maximize(ans, info_f_sub[i] + f[v][K - i - 1] + sum_neighbor[u] - p[v]);
}
//not drop breadcumb at u
for(int i = 0; i <= K; ++i){
//both is empty
maximize(ans, info_g[i] + g[v][K - i]);
//previous is empty, p[v] is still
maximize(ans, info_g[i] + f[v][K - i]);
//previous is not empty, but p[v] is empty
maximize(ans, info_f[i] + g[v][K - i]);
//bot not empty
maximize(ans, info_f[i] + f[v][K - i] - p[u]); //duplicated
}
}
exist_subtrees = true;
//update info
for(int i = 1; i <= K; ++i){
maximize(info_f[i], f[v][i]);
maximize(info_g[i], g[v][i]);
maximize(info_f_sub[i], f[v][i] - p[v]);
maximize(info_g_sub[i], g[v][i] - p[v]);
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
#endif // LOCAL
cin >> N >> K;
for(int i = 0; i < N; ++i) cin >> p[i];
for(int i = 0; i < N - 1; ++i){
int u, v;
cin >> u >> v;
--u, --v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
sum_neighbor[u] += p[v];
sum_neighbor[v] += p[u];
}
if(K == 0){
cout << 0 << '\n';
return 0;
}
dfs(1, -1);
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
186 ms |
102728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
