답안 #43255 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43255	2018-03-11T16:02:34 Z	krauch	Chase (CEOI17_chase)	C++14	100 / 100	2661 ms	379000 KB

chase

/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
#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 > 1000 ? 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;
}

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2684 KB	Output is correct
2	Correct	3 ms	2788 KB	Output is correct
3	Correct	3 ms	2788 KB	Output is correct
4	Correct	3 ms	2880 KB	Output is correct
5	Correct	4 ms	2900 KB	Output is correct
6	Correct	3 ms	2936 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2684 KB	Output is correct
2	Correct	3 ms	2788 KB	Output is correct
3	Correct	3 ms	2788 KB	Output is correct
4	Correct	3 ms	2880 KB	Output is correct
5	Correct	4 ms	2900 KB	Output is correct
6	Correct	3 ms	2936 KB	Output is correct
7	Correct	2442 ms	6580 KB	Output is correct
8	Correct	214 ms	6580 KB	Output is correct
9	Correct	225 ms	6580 KB	Output is correct
10	Correct	2661 ms	6580 KB	Output is correct
11	Correct	992 ms	6636 KB	Output is correct
12	Correct	362 ms	6636 KB	Output is correct

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	712 ms	362364 KB	Output is correct
2	Correct	702 ms	362364 KB	Output is correct
3	Correct	477 ms	362364 KB	Output is correct
4	Correct	343 ms	362364 KB	Output is correct
5	Correct	832 ms	362364 KB	Output is correct
6	Correct	820 ms	362364 KB	Output is correct
7	Correct	842 ms	362364 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2684 KB	Output is correct
2	Correct	3 ms	2788 KB	Output is correct
3	Correct	3 ms	2788 KB	Output is correct
4	Correct	3 ms	2880 KB	Output is correct
5	Correct	4 ms	2900 KB	Output is correct
6	Correct	3 ms	2936 KB	Output is correct
7	Correct	2442 ms	6580 KB	Output is correct
8	Correct	214 ms	6580 KB	Output is correct
9	Correct	225 ms	6580 KB	Output is correct
10	Correct	2661 ms	6580 KB	Output is correct
11	Correct	992 ms	6636 KB	Output is correct
12	Correct	362 ms	6636 KB	Output is correct
13	Correct	712 ms	362364 KB	Output is correct
14	Correct	702 ms	362364 KB	Output is correct
15	Correct	477 ms	362364 KB	Output is correct
16	Correct	343 ms	362364 KB	Output is correct
17	Correct	832 ms	362364 KB	Output is correct
18	Correct	820 ms	362364 KB	Output is correct
19	Correct	842 ms	362364 KB	Output is correct
20	Correct	845 ms	362364 KB	Output is correct
21	Correct	82 ms	362364 KB	Output is correct
22	Correct	832 ms	362676 KB	Output is correct
23	Correct	335 ms	364652 KB	Output is correct
24	Correct	834 ms	366912 KB	Output is correct
25	Correct	472 ms	368716 KB	Output is correct
26	Correct	686 ms	376928 KB	Output is correct
27	Correct	687 ms	379000 KB	Output is correct

답안 #43255

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 20.0 / 20.0

Subtask #3 30.0 / 30.0

Subtask #4 30.0 / 30.0

Subtask #1
20.0 / 20.0

Subtask #2
20.0 / 20.0

Subtask #3
30.0 / 30.0

Subtask #4
30.0 / 30.0