oj.uz

Submission #468552

# Submission time Handle Problem Language Result Execution time Memory
468552 2021-08-28T17:17:23 Z idk321 Chase (CEOI17_chase) C++17
0 / 100
 190 ms 170308 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100005;
const int V = 101;
int p[N];
int n, v;
vector<int> adj[N];
ll dp[N][2][V];

void dfs(int node, int par) {

    for (int next : adj[node]) {
        if (next == par) continue;
        dp[node][1][1] += p[next];
        dfs(next, node);
    }
    for (int next : adj[node]) {
        if (next == par) continue;
        for (int i = 0; i <= v; i++) {
            dp[node][0][i] = max(dp[node][0][i], dp[node][0][0] + dp[next][0][i]);
            dp[node][0][i] = max(dp[node][0][i], dp[node][0][0] + dp[next][1][i]);
            if (i != v) {
                dp[node][1][i + 1] = max(dp[node][1][i + 1], dp[node][1][1] + dp[next][0][i]);
                dp[node][1][i + 1] = max(dp[node][1][i + 1], dp[node][1][1] + dp[next][1][i]);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    ll res = 0;
    for (int root = 6; root <= 6; root++) {
        for (int a = 0; a <= n; a++) for (int b = 0; b < 2; b++) for (int c = 0; c <= v; c++) dp[a][b][c] = 0;
        dfs(root, -1);
        ll sum = 0;
        for (int i = 1; i <= n; i++) sum += p[i];
        for (int i = 0; i <= v; i++) {
            for (int j = 0; j < 2; j++) res = max(res, dp[root][j][i]);
        }
    }


    cout << res << "\n";
}

/*
12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12
*/

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 190 ms 170308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -