oj.uz

Submission #511906

# Submission time Handle Problem Language Result Execution time Memory
511906 2022-01-16T05:12:10 Z Monarchuwu Chase (CEOI17_chase) C++17
70 / 100
 216 ms 91456 KB 
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;

const int N = 1e5 + 9, K = 100 + 2;
int n, V;
int p[N];
vector<int> g[N];
ll sum_p[N];

ll dp1[N][K];   // dp1[u][j]: bắt đầu tại u, sẽ dùng j lượt
void dfs_1(int u, int par) {
    fill(dp1[u] + 1, dp1[u] + V + 1, 0);

    for (int v : g[u]) if (v != par) {
        dfs_1(v, u);
        for (int j = 1; j <= V; ++j) {
            dp1[u][j] = max({ dp1[u][j], dp1[v][j], dp1[v][j - 1] + sum_p[v] - p[u] });
        }
    }
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> p[i];
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int u = 1; u <= n; ++u)
        for (int v : g[u]) sum_p[u] += p[v];

    ll ans(0);
    if (n <= 1000) {
        for (int i = 1; i <= n; ++i) {
            dfs_1(i, 0);
            for (int j = 0; j <= V; ++j) {
                ans = max(ans, dp1[i][j]);
                if (j < V) ans = max(ans, dp1[i][j] + sum_p[i]);
            }
        }
    }
    else {
        dfs_1(1, 0);
        for (int j = 0; j <= V; ++j) {
            ans = max(ans, dp1[1][j]);
            if (j < V) ans = max(ans, dp1[1][j] + sum_p[1]);
        }
    }
    cout << ans << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/
/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
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
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
36
--------------------------------------------------|
==================================================+
*/

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 2664 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 2664 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 196 ms 3564 KB Output is correct
8 Correct 28 ms 3576 KB Output is correct
9 Correct 20 ms 3444 KB Output is correct
10 Correct 216 ms 3540 KB Output is correct
11 Correct 78 ms 3532 KB Output is correct
12 Correct 38 ms 3440 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 91456 KB Output is correct
2 Correct 123 ms 91400 KB Output is correct
3 Correct 78 ms 87096 KB Output is correct
4 Correct 90 ms 86920 KB Output is correct
5 Correct 125 ms 87024 KB Output is correct
6 Correct 145 ms 86932 KB Output is correct
7 Correct 139 ms 86992 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 2664 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 196 ms 3564 KB Output is correct
8 Correct 28 ms 3576 KB Output is correct
9 Correct 20 ms 3444 KB Output is correct
10 Correct 216 ms 3540 KB Output is correct
11 Correct 78 ms 3532 KB Output is correct
12 Correct 38 ms 3440 KB Output is correct
13 Correct 116 ms 91456 KB Output is correct
14 Correct 123 ms 91400 KB Output is correct
15 Correct 78 ms 87096 KB Output is correct
16 Correct 90 ms 86920 KB Output is correct
17 Correct 125 ms 87024 KB Output is correct
18 Correct 145 ms 86932 KB Output is correct
19 Correct 139 ms 86992 KB Output is correct
20 Incorrect 127 ms 88900 KB Output isn't correct
21 Halted 0 ms 0 KB -