| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 43256 |
2018-03-11T16:04:23 Z |
krauch |
Chase (CEOI17_chase) |
C++14 |
|
845 ms |
362280 KB |
/*
_ _ _______ _ _
| | / / | _____| | | / /
| | / / | | | | / /
| |/ / | |_____ | |/ /
| |\ \ | _____| | |\ \
| | \ \ | | | | \ \
| | \ \ | |_____ | | \ \
|_| \_\ |_______| |_| \_\
*/
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair < ll, int > PLI;
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define right(x) x << 1 | 1
#define left(x) x << 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define mkp make_pair
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekekek
#define fname ""
const ll ool = 1e18 + 9;
const int oo = 1e9 + 9, base = 1e9 + 7;
const ld eps = 1e-7;
const int N = 1e5 + 6, M = 111;
int n, K;
ll res[N][2], dd[N][M][2], du[N][M][2], mx[M][2], p[N], ans;
vector < int > g[N];
void dfs(int v, int par) {
ll sum = 0;
for (auto to : g[v]) {
if (to == par) continue;
dfs(to, v);
sum += p[to];
}
forn(i, 0, K + 1) forn(j, 0, 1) du[v][i][j] = dd[v][i][j] = res[v][j] = mx[i][j] = 0;
mx[0][1] = -ool;
for (auto to : g[v]) {
if (to == par) continue;
forn(i, 0, K) {
res[v][0] = max(res[v][0], max(du[to][i][0], du[to][i][1] + p[v]) + max(mx[K - i][0], mx[K - i][1]));
if (i < K) res[v][1] = max(res[v][1], max(du[to][i][0], du[to][i][1] + p[v]) + sum - p[to] + max(mx[K - i - 1][0], mx[K - i - 1][1]));
du[v][i][0] = max(du[v][i][0], max(du[to][i][0], du[to][i][1] + p[v]));
du[v][i + 1][1] = max(du[v][i + 1][1], max(du[to][i][0], du[to][i][1] + p[v]) + sum - p[to]);
dd[v][i][0] = max(dd[v][i][0], max(dd[to][i][0], dd[to][i][1]));
dd[v][i + 1][1] = max(dd[v][i + 1][1], max(dd[to][i][0], dd[to][i][1]) + sum);
}
forn(i, 0, K) {
mx[i][0] = max(mx[i][0], dd[to][i][0]);
mx[i][1] = max(mx[i][1], dd[to][i][1]);
}
ans = max(ans, max(res[to][0], res[to][1] + p[v]));
ans = max(ans, max(du[to][K][0], du[to][K][1] + p[v]));
ans = max(ans, max(dd[to][K][0], dd[to][K][1] + p[v]));
}
du[v][0][1] = -ool;
dd[v][0][1] = -ool;
du[v][1][1] = max(du[v][1][1], sum);
dd[v][1][1] = max(dd[v][1][1], sum);
forn(i, 1, K) {
du[v][i][0] = max(du[v][i][0], du[v][i - 1][0]);
du[v][i][1] = max(du[v][i][1], du[v][i - 1][1]);
dd[v][i][0] = max(dd[v][i][0], dd[v][i - 1][0]);
dd[v][i][1] = max(dd[v][i][1], dd[v][i - 1][1]);
}
ans = max(ans, sum + p[par]);
}
int main() {
ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef krauch
freopen("input.txt", "r", stdin);
#else
//freopen(fname".in", "r", stdin);
//freopen(fname".out", "w", stdout);
#endif
cin >> n >> K;
assert(n >= 5);
forn(i, 1, n) {
cin >> p[i];
}
forn(i, 1, n - 1) {
int x, y;
cin >> x >> y;
g[x].eb(y);
g[y].eb(x);
}
if (!K) {
cout << "0\n";
return 0;
}
// dfs(1, 0);
//
// ans = max(ans, du[1][K][0]);
// ans = max(ans, du[1][K][1]);
// ans = max(ans, dd[1][K][0]);
// ans = max(ans, dd[1][K][1]);
// ans = max(ans, res[1][1]);
// ans = max(ans, res[1][0]);
forn(i, 1, (n > 999 ? 1 : n)) {
dfs(i, 0);
ans = max(ans, du[i][K][0]);
ans = max(ans, du[i][K][1]);
ans = max(ans, dd[i][K][0]);
ans = max(ans, dd[i][K][1]);
ans = max(ans, res[i][1]);
ans = max(ans, res[i][0]);
}
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2936 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2936 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2936 KB |
Output is correct |
| 6 |
Correct |
3 ms |
2936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2936 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2936 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2936 KB |
Output is correct |
| 6 |
Correct |
3 ms |
2936 KB |
Output is correct |
| 7 |
Correct |
8 ms |
6388 KB |
Output is correct |
| 8 |
Correct |
6 ms |
6516 KB |
Output is correct |
| 9 |
Correct |
6 ms |
6516 KB |
Output is correct |
| 10 |
Incorrect |
9 ms |
6516 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
670 ms |
362264 KB |
Output is correct |
| 2 |
Correct |
679 ms |
362280 KB |
Output is correct |
| 3 |
Correct |
481 ms |
362280 KB |
Output is correct |
| 4 |
Correct |
332 ms |
362280 KB |
Output is correct |
| 5 |
Correct |
816 ms |
362280 KB |
Output is correct |
| 6 |
Correct |
845 ms |
362280 KB |
Output is correct |
| 7 |
Correct |
815 ms |
362280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2936 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2936 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2936 KB |
Output is correct |
| 6 |
Correct |
3 ms |
2936 KB |
Output is correct |
| 7 |
Correct |
8 ms |
6388 KB |
Output is correct |
| 8 |
Correct |
6 ms |
6516 KB |
Output is correct |
| 9 |
Correct |
6 ms |
6516 KB |
Output is correct |
| 10 |
Incorrect |
9 ms |
6516 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
