oj.uz

Submission #143494

# Submission time Handle Problem Language Result Execution time Memory
143494 2019-08-14T10:10:04 Z popovicirobert Chase (CEOI17_chase) C++14
100 / 100
 611 ms 172152 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long



/*const int MOD = ;

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(int &x, int y) {
    x += MOD - y;
    mod(x);
}

inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}

inline int inv(int x) {
    return lgput(x, MOD - 2);
}*/

/*int fact[], invfact[];

inline void prec(int n) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
    }
    invfact[n] = lgput(fact[n], MOD - 2);
    for(int i = n - 1; i >= 0; i--) {
        invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
    }
}

inline int comb(int n, int k) {
    if(n < k) return 0;
    return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}*/

using namespace std;

const ll INF = 1e18;
const int MAXN = (int) 1e5;

vector <int> g[MAXN + 1];
int vals[MAXN + 1], v;
ll sum[MAXN + 1];

ll up[MAXN + 1][101], down[MAXN + 1][101];
ll ans = 0;

void dfs(int nod, int par) {

    up[nod][0] = 0;
    up[nod][1] = sum[nod];
    down[nod][0] = 0;
    down[nod][1] = sum[nod] - vals[par];

    for(auto it : g[nod]) {
        if(it != par) {
            dfs(it, nod);
            ll mx = 0;
            for(int i = 0; i <= v; i++) {
                mx = max(mx, up[nod][i]);
                ans = max(ans, mx + down[it][v - i]);

            }
            for(int i = 0; i <= v; i++) {
                up[nod][i] = max(up[nod][i], up[it][i]);
                if(i > 0) {
                    up[nod][i] = max(up[nod][i], up[it][i - 1] + sum[nod] - vals[it]);
                }
                down[nod][i] = max(down[nod][i], down[it][i]);
                if(i > 0) {
                    down[nod][i] = max(down[nod][i], down[it][i - 1] + sum[nod] - vals[par]);
                    ans = max(ans, down[it][i - 1] + sum[nod]);
                }
            }
        }
    }

    for(int i = 1; i <= v; i++) {
        up[nod][i] = max(up[nod][i], up[nod][i - 1]);
        down[nod][i] = max(down[nod][i], down[nod][i - 1]);
    }
    ans = max(ans, max(up[nod][v], down[nod][v]));
}


int main() {
#if 0
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, j, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> v;
    for(i = 1; i <= n; i++) {
        cin >> vals[i];
    }
    for(i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y), sum[x] += vals[y];
        g[y].push_back(x), sum[y] += vals[x];
    }

    for(i = 1; i <= n; i++) {
        for(j = 0; j <= v; j++) {
            up[i][j] = down[i][j] = -INF;
        }
    }
    dfs(1, 0);

    for(i = 1; i <= n; i++) {
        reverse(g[i].begin(), g[i].end());
        for(j = 0; j <= v; j++) {
            up[i][j] = down[i][j] = -INF;
        }
    }
    dfs(1, 0);

    cout << ans;

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 4 ms 2680 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 5 ms 2680 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 8 ms 4404 KB Output is correct
8 Correct 7 ms 4476 KB Output is correct
9 Correct 6 ms 4344 KB Output is correct
10 Correct 8 ms 4344 KB Output is correct
11 Correct 7 ms 4344 KB Output is correct
12 Correct 6 ms 4344 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 172004 KB Output is correct
2 Correct 508 ms 172152 KB Output is correct
3 Correct 403 ms 167664 KB Output is correct
4 Correct 243 ms 167416 KB Output is correct
5 Correct 545 ms 167288 KB Output is correct
6 Correct 542 ms 167416 KB Output is correct
7 Correct 540 ms 167264 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 5 ms 2680 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 8 ms 4404 KB Output is correct
8 Correct 7 ms 4476 KB Output is correct
9 Correct 6 ms 4344 KB Output is correct
10 Correct 8 ms 4344 KB Output is correct
11 Correct 7 ms 4344 KB Output is correct
12 Correct 6 ms 4344 KB Output is correct
13 Correct 611 ms 172004 KB Output is correct
14 Correct 508 ms 172152 KB Output is correct
15 Correct 403 ms 167664 KB Output is correct
16 Correct 243 ms 167416 KB Output is correct
17 Correct 545 ms 167288 KB Output is correct
18 Correct 542 ms 167416 KB Output is correct
19 Correct 540 ms 167264 KB Output is correct
20 Correct 541 ms 167464 KB Output is correct
21 Correct 242 ms 167288 KB Output is correct
22 Correct 556 ms 167288 KB Output is correct
23 Correct 255 ms 167288 KB Output is correct
24 Correct 553 ms 167436 KB Output is correct
25 Correct 399 ms 167260 KB Output is correct
26 Correct 533 ms 172024 KB Output is correct
27 Correct 530 ms 171896 KB Output is correct