| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 113927 |
2019-05-29T08:42:16 Z |
MAMBA |
Chase (CEOI17_chase) |
C++17 |
|
719 ms |
328952 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[N][2][101], dp_down[N][2][101], v2, p[N], p2[N];
vi adj[N];
inline void update(ll A[][101] , ll B[][101] ,int so ,int sy) {
rep(j , 0 , v2) {
smax(A[0][j] , B[0][j]);
smax(A[0][j] , B[1][j] - p[so]);
if (j) {
smax(A[1][j] , B[0][j - 1] + p2[so] - p[sy]);
smax(A[1][j] , B[1][j - 1] + p2[so] - p[so]);
}
}
}
void dfs_down(int v, int par = 0) {
dp_down[v][1][0] = dp_up[v][1][0] = -1e18;
rep(i , 1 , v2)
dp_down[v][1][i] = dp_up[v][1][i] = p2[v];
for (auto e : adj[v])
if (e ^ par) {
dfs_down(e , v);
update(dp_down[v] , dp_down[e] , v , e);
}
}
ll junk[2][101];
void dfs_up(int v, int par = 0) {
auto f = [v , par]() -> void {
memcpy(junk , dp_up[v] , sizeof(dp_up[v]));
for (auto e : adj[v])
if (e ^ par) {
update(dp_up[e] , junk , e , v);
update(junk , dp_down[e] , v , e);
}
};
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);
cin >> n >> v2;
if (v2 == 0) return cout << 0 << endl, 0;
v2++;
rep(i , 1 , n + 1)
cin >> 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);
dfs_up(1);
ll res = 0;
rep(i , 1, n + 1)
smax(res , max(dp_up[i][1][v2 - 1] , dp_up[i][0][v2 - 1]));
cout << res << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
719 ms |
328952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
