oj.uz

Submission #468554

# Submission time Handle Problem Language Result Execution time Memory
468554 2021-08-28T17:19:48 Z idk321 Chase (CEOI17_chase) C++17
70 / 100
 534 ms 170300 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 = 1; root <= (n <= 1000 ? n : 1); 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
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 496 ms 4312 KB Output is correct
8 Correct 70 ms 4420 KB Output is correct
9 Correct 53 ms 4172 KB Output is correct
10 Correct 534 ms 4276 KB Output is correct
11 Correct 234 ms 4172 KB Output is correct
12 Correct 91 ms 4172 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 168232 KB Output is correct
2 Correct 188 ms 170300 KB Output is correct
3 Correct 152 ms 166788 KB Output is correct
4 Correct 132 ms 166420 KB Output is correct
5 Correct 202 ms 166588 KB Output is correct
6 Correct 202 ms 166464 KB Output is correct
7 Correct 194 ms 166496 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 496 ms 4312 KB Output is correct
8 Correct 70 ms 4420 KB Output is correct
9 Correct 53 ms 4172 KB Output is correct
10 Correct 534 ms 4276 KB Output is correct
11 Correct 234 ms 4172 KB Output is correct
12 Correct 91 ms 4172 KB Output is correct
13 Correct 207 ms 168232 KB Output is correct
14 Correct 188 ms 170300 KB Output is correct
15 Correct 152 ms 166788 KB Output is correct
16 Correct 132 ms 166420 KB Output is correct
17 Correct 202 ms 166588 KB Output is correct
18 Correct 202 ms 166464 KB Output is correct
19 Correct 194 ms 166496 KB Output is correct
20 Incorrect 191 ms 166480 KB Output isn't correct
21 Halted 0 ms 0 KB -