oj.uz

Submission #146249

# Submission time Handle Problem Language Result Execution time Memory
146249 2019-08-23T06:06:09 Z lyc Chase (CEOI17_chase) C++14
100 / 100
 808 ms 344056 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+5;
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]),
                        (h[u][x-1][0] != v ? f[h[u][x-1][0]][x-1] : f[h[u][x-1][1]][x-1]) + (surr[u] - P[v] + P[p]),
                    });
        }

        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] << " " << (V-1 >= 0 ? g[i][V-1] + surr[i] + P[pa[i]] : 0) << endl;
        ans = max({
                ans,
                f[h[i][V][0]][V],
                (V-1 >= 0 ? f[h[i][V-1][0]][V-1] + surr[i] + P[pa[i]] : 0),
                g[i][V],
                (V-1 >= 0 ? g[i][V-1] + surr[i] + P[pa[i]] : 0)
                });
    }
    cout << ans << '\n';
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2780 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2780 KB Output is correct
7 Correct 9 ms 6136 KB Output is correct
8 Correct 8 ms 6136 KB Output is correct
9 Correct 7 ms 6008 KB Output is correct
10 Correct 9 ms 6136 KB Output is correct
11 Correct 8 ms 6136 KB Output is correct
12 Correct 7 ms 6008 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 343848 KB Output is correct
2 Correct 749 ms 344056 KB Output is correct
3 Correct 808 ms 339040 KB Output is correct
4 Correct 373 ms 338412 KB Output is correct
5 Correct 662 ms 338552 KB Output is correct
6 Correct 598 ms 338428 KB Output is correct
7 Correct 626 ms 338548 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2780 KB Output is correct
7 Correct 9 ms 6136 KB Output is correct
8 Correct 8 ms 6136 KB Output is correct
9 Correct 7 ms 6008 KB Output is correct
10 Correct 9 ms 6136 KB Output is correct
11 Correct 8 ms 6136 KB Output is correct
12 Correct 7 ms 6008 KB Output is correct
13 Correct 629 ms 343848 KB Output is correct
14 Correct 749 ms 344056 KB Output is correct
15 Correct 808 ms 339040 KB Output is correct
16 Correct 373 ms 338412 KB Output is correct
17 Correct 662 ms 338552 KB Output is correct
18 Correct 598 ms 338428 KB Output is correct
19 Correct 626 ms 338548 KB Output is correct
20 Correct 618 ms 338556 KB Output is correct
21 Correct 279 ms 174392 KB Output is correct
22 Correct 611 ms 338364 KB Output is correct
23 Correct 372 ms 338320 KB Output is correct
24 Correct 600 ms 338356 KB Output is correct
25 Correct 707 ms 338416 KB Output is correct
26 Correct 571 ms 343800 KB Output is correct
27 Correct 575 ms 343928 KB Output is correct