| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 113912 |
2019-05-29T07:55:34 Z |
MAMBA |
Chase (CEOI17_chase) |
C++17 |
|
311 ms |
168424 KB |
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef complex<ld> point;
typedef pair<ld , ld> pld;
typedef vector<ll> vi;
inline void fileIO(string s) {
// freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }
constexpr int N = 1e5 + 10;
constexpr int MOD = 1e9 + 7;
template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }
int n;
ll dp_up[100][N], dp_down[100][N], v2, p[N], p2[N];
vi adj[N];
void dfs_down(int v, int par = 0) {
dp_down[0][v] = p2[v] - p[v];
for (auto e : adj[v])
if (e ^ par) {
dfs_down(e , v);
rep(j , 1 , v2)
smax(dp_down[j][v] , dp_down[j - 1][e] + p2[v] - 2 * p[v]);
}
}
ll junk[100];
void dfs_up(int v, int par = 0) {
auto f = [v , par]() -> void {
rep(i , 0 , v2)
junk[i] = dp_up[i][v];
for (auto e : adj[v])
if (e ^ par) {
dp_up[0][e] = dp_down[0][e];
rep(j , 1 , v2)
smax(dp_up[j][e] , junk[j - 1] + p2[e] - 2 * p[e]);
rep(j , 0 , v2 - 1)
smax(junk[j + 1] , dp_down[j][e] + p2[v] - 2 * p[v]);
}
};
f();
reverse(all(adj[v]));
f();
for (auto e : adj[v])
if (e ^ par)
dfs_up(e , v);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
memset(dp_up , -63, sizeof(dp_up));
memset(dp_down , -63, sizeof(dp_down));
cin >> n >> v2;
if (v2 == 0) return cout << 0 << endl, 0;
rep(i , 1 , n + 1) {
cin >> p[i];
p2[i] = p[i];
}
rep(i , 1 , n) {
int u , v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
p2[u] += p[v];
p2[v] += p[u];
}
dfs_down(1);
//dp_up[0][1] = dp_down[0][1];
//dfs_up(1);
ll res = 0;
rep(i , 0 , v2)
smax(res , dp_down[i][1]);
// rep(j , 1 , n + 1)
// smax(res , max(dp_up[i][j] , dp_down[i][j]));
cout << res << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
159384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
159384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
311 ms |
168424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
159384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
