oj.uz

Submission #468553

# Submission time Handle Problem Language Result Execution time Memory
468553 2021-08-28T17:18:52 Z idk321 Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 168260 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; 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 2600 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2596 KB Output is correct
5 Correct 2 ms 2676 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 2600 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2596 KB Output is correct
5 Correct 2 ms 2676 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 499 ms 4328 KB Output is correct
8 Correct 61 ms 4332 KB Output is correct
9 Correct 54 ms 4296 KB Output is correct
10 Correct 499 ms 4300 KB Output is correct
11 Correct 208 ms 4296 KB Output is correct
12 Correct 111 ms 4300 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4072 ms 168260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2600 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2596 KB Output is correct
5 Correct 2 ms 2676 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 499 ms 4328 KB Output is correct
8 Correct 61 ms 4332 KB Output is correct
9 Correct 54 ms 4296 KB Output is correct
10 Correct 499 ms 4300 KB Output is correct
11 Correct 208 ms 4296 KB Output is correct
12 Correct 111 ms 4300 KB Output is correct
13 Execution timed out 4072 ms 168260 KB Time limit exceeded
14 Halted 0 ms 0 KB -