답안 #43257 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43257	2018-03-11T16:07:40 Z	krauch	Chase (CEOI17_chase)	C++14	100 / 100	2297 ms	362532 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, 3) {
        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	3 ms	2680 KB	Output is correct
2	Correct	3 ms	2784 KB	Output is correct
3	Correct	3 ms	2784 KB	Output is correct
4	Correct	3 ms	2872 KB	Output is correct
5	Correct	3 ms	2872 KB	Output is correct
6	Correct	3 ms	2872 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2680 KB	Output is correct
2	Correct	3 ms	2784 KB	Output is correct
3	Correct	3 ms	2784 KB	Output is correct
4	Correct	3 ms	2872 KB	Output is correct
5	Correct	3 ms	2872 KB	Output is correct
6	Correct	3 ms	2872 KB	Output is correct
7	Correct	13 ms	6436 KB	Output is correct
8	Correct	7 ms	6436 KB	Output is correct
9	Correct	7 ms	6436 KB	Output is correct
10	Correct	14 ms	6436 KB	Output is correct
11	Correct	9 ms	6664 KB	Output is correct
12	Correct	7 ms	6664 KB	Output is correct

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1801 ms	362344 KB	Output is correct
2	Correct	1800 ms	362396 KB	Output is correct
3	Correct	998 ms	362396 KB	Output is correct
4	Correct	427 ms	362396 KB	Output is correct
5	Correct	2129 ms	362396 KB	Output is correct
6	Correct	2180 ms	362396 KB	Output is correct
7	Correct	2175 ms	362396 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2680 KB	Output is correct
2	Correct	3 ms	2784 KB	Output is correct
3	Correct	3 ms	2784 KB	Output is correct
4	Correct	3 ms	2872 KB	Output is correct
5	Correct	3 ms	2872 KB	Output is correct
6	Correct	3 ms	2872 KB	Output is correct
7	Correct	13 ms	6436 KB	Output is correct
8	Correct	7 ms	6436 KB	Output is correct
9	Correct	7 ms	6436 KB	Output is correct
10	Correct	14 ms	6436 KB	Output is correct
11	Correct	9 ms	6664 KB	Output is correct
12	Correct	7 ms	6664 KB	Output is correct
13	Correct	1801 ms	362344 KB	Output is correct
14	Correct	1800 ms	362396 KB	Output is correct
15	Correct	998 ms	362396 KB	Output is correct
16	Correct	427 ms	362396 KB	Output is correct
17	Correct	2129 ms	362396 KB	Output is correct
18	Correct	2180 ms	362396 KB	Output is correct
19	Correct	2175 ms	362396 KB	Output is correct
20	Correct	2221 ms	362396 KB	Output is correct
21	Correct	58 ms	362396 KB	Output is correct
22	Correct	2173 ms	362396 KB	Output is correct
23	Correct	436 ms	362396 KB	Output is correct
24	Correct	2297 ms	362396 KB	Output is correct
25	Correct	1012 ms	362396 KB	Output is correct
26	Correct	1846 ms	362436 KB	Output is correct
27	Correct	1831 ms	362532 KB	Output is correct

답안 #43257

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