# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
146129 |
2019-08-22T09:49:11 Z |
lyc |
Chase (CEOI17_chase) |
C++14 |
|
88 ms |
14780 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
const int MAXN = 1e5;
const int MAXV = 105;
int N, V;
int P[MAXN];
vector<int> al[MAXN]; int pa[MAXN];
ll f[MAXN][MAXV], g[MAXN][MAXV], h[MAXN][MAXV][2];
ll surr[MAXN];
void down(int u, int p) {
pa[u] = p;
surr[u] = 0;
for (auto v : al[u]) if (v != p) {
down(v,u);
surr[u] += P[v];
}
f[u][0] = 0;
FOR(x,1,V) {
for (auto v : al[u]) if (v != p) {
f[u][x] = max({ f[u][x], f[v][x], f[v][x-1]+surr[u] });
}
}
}
void up(int u, int p) {
FOR(x,1,V){
h[u][x][0] = h[u][x][1] = 0;
for (auto v : al[u]) if (v != p) {
if (h[u][x][0] == 0 or f[v][x] > f[h[u][x][0]][x]) h[u][x][0] = v;
else if (h[u][x][1] == 0 or f[v][x] > f[h[u][x][1]][x]) h[u][x][1] = v;
}
}
for (auto v : al[u]) if (v != p) {
g[v][0] = 0;
FOR(x,1,V) {
g[v][x] = max({
g[u][x],
(h[u][x][0] != v ? f[h[u][x][0]][x] : f[h[u][x][1]][x]),
g[u][x-1] + (surr[u] - P[v] + P[p]),
#define fp(y) f[y][x-1]-P[y]
(h[u][x-1][0] != v ? fp(h[u][x-1][0]) : fp(h[u][x-1][1])) + (surr[u] - P[v] + P[p]),
});
//if (u == 2) cout << g[u][x] << " " << g[u][x-1] << " bbb " << v << " " << x << " :: " << g[v][x] << " zzzz " << g[u][x] << " " << (h[u][x][0] != v ? f[h[u][x][0]][x] : f[h[u][x][1]][x]) << " " << g[u][x-1] + (surr[u] - P[v] + P[p]) << " " << (h[u][x-1][0] != v ? fp(h[u][x-1][0]) : fp(h[u][x-1][1])) << endl;
//if (u == 2) cout << h[u][x][0] << " " << h[u][x][1] << endl;
//if (u == 7) cout << g[u][x] << " " << g[u][x-1] << " aaa " << v << " " << x << " :: " << g[v][x] << endl;
}
up(v,u);
}
}
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> V;
FOR(i,1,N) { cin >> P[i]; }
FOR(i,1,N-1) {
int A, B; cin >> A >> B;
al[A].push_back(B);
al[B].push_back(A);
}
down(1,0);
up(1,0);
ll ans = 0;
FOR(i,1,N){
//cout << "i " << i << " :: " << f[i][V] << " " << g[i][V] << " " << g[i][V-1] << "+" << surr[i] << endl;
ans = max({
ans,
f[i][V],
g[i][V],
g[i][V-1] + surr[i] + P[pa[i]]
});
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
4 ms |
2808 KB |
Output is correct |
3 |
Correct |
4 ms |
2808 KB |
Output is correct |
4 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
4 ms |
2808 KB |
Output is correct |
3 |
Correct |
4 ms |
2808 KB |
Output is correct |
4 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
88 ms |
14780 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
4 ms |
2808 KB |
Output is correct |
3 |
Correct |
4 ms |
2808 KB |
Output is correct |
4 |
Incorrect |
4 ms |
2680 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |