oj.uz

Submission #161170

# Submission time Handle Problem Language Result Execution time Memory
161170 2019-11-01T08:29:37 Z Minnakhmetov Chase (CEOI17_chase) C++14
50 / 100
 670 ms 262348 KB 
#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
using namespace std;

const ll INF = 1e18;
const int N = 1e5 + 5, M = 105;
int a[N];
vector<int> g[N];
ll dp1[N][M], dp2[N][M][2], sum[N], dp3[M];
int n, m;

void upd(ll &a, ll b) {
    a = max(a, b);
}

ll ans = 0;

void dfs(int node, int anc) {
    if (anc != -1)
        g[node].erase(find(all(g[node]), anc));
    for (int to : g[node]) {
        sum[node] += a[to];
        dfs(to, node);
    }

    dp1[node][1] = sum[node];
    dp2[node][1][1] = sum[node];
    dp2[node][0][1] = -INF;

    ll up = (anc == -1 ? 0 : a[anc]);

    for (int k = 0; k < 2; k++) {
        memset(dp3, 0, sizeof(dp3));

        for (int to : g[node]) {
            for (int i = 0; i <= m; i++) {
                ll cur = dp3[m - i] + dp1[to][i];
                upd(ans, cur);

                // if (cur == 40) {
                //     cout << node + 1 << " " << to + 1 << " " << i << "\n";
                //     cout << m - i << " " << j << " " << dp3[m - i][j] << "\n\n";
                // }
            }
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j < 2; j++) {
                    ll cur = dp2[to][i][j] + (j ? a[node] : 0);
                    upd(dp3[i], cur);
                    if (i < m) {
                        // if (node == 0 && sum[node] - a[to] + up + cur == 30) {
                        //     cout << to + 1 << " " << i << " " << cur << "\n";
                        // }
                        upd(dp3[i + 1], sum[node] - a[to] + up + cur);
                    }
                }
            }

            for (int i = 1; i <= m; i++) {
                upd(dp3[i], dp3[i - 1]);
            }
        }
        reverse(all(g[node]));
    }

    for (int to : g[node]) {
        for (int i = 0; i <= m; i++) {
            upd(dp1[node][i], dp1[to][i]);
            if (i < m)
                upd(dp1[node][i + 1] , dp1[to][i] + sum[node]);
            for (int j = 0; j < 2; j++) {
                ll cur = dp2[to][i][j] + (j ? a[node] : 0);
                upd(dp2[node][i][0], cur);
                if (i < m)
                    upd(dp2[node][i + 1][1], cur + sum[node] - a[to]);
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        upd(dp2[node][i][0], dp2[node][i - 1][0]);
        upd(dp2[node][i][1], dp2[node][i - 1][1]);
        upd(dp1[node][i], dp1[node][i - 1]);
    }

    for (int i = 0; i <= m; i++) {
        upd(ans, dp2[node][i][0]);
        upd(ans, dp2[node][i][1]);
        upd(ans, dp1[node][i]);
    }

    // cout << node + 1 << " : \n";
    // for (int i = 0; i <= m; i++) {
    //     for (int j = 0; j < 2; j++) {
    //         cout << i << " " << j << " " << dp2[node][i][j] << "\n";
    //     }
    // }
    // cout << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(0, -1);

    cout << ans << "\n";

    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 4 ms 2808 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 2680 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 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 2680 KB Output is correct
7 Incorrect 9 ms 5240 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 260244 KB Output is correct
2 Correct 649 ms 262348 KB Output is correct
3 Correct 670 ms 255288 KB Output is correct
4 Correct 326 ms 255884 KB Output is correct
5 Correct 634 ms 255816 KB Output is correct
6 Correct 655 ms 255816 KB Output is correct
7 Correct 641 ms 255736 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 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 2680 KB Output is correct
7 Incorrect 9 ms 5240 KB Output isn't correct
8 Halted 0 ms 0 KB -