oj.uz

Submission #511624

# Submission time Handle Problem Language Result Execution time Memory
511624 2022-01-16T03:17:41 Z Monarchuwu Chase (CEOI17_chase) C++17
0 / 100
 4000 ms 52140 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];

int dp[N][K], ans;
void dfs(int u, int par) {
    ans = max(ans, *max_element(dp[u], dp[u] + v + 1));
    int s(0);
    for (int v : g[u])
        if (v != par) s += p[v];

    for (int v : g[u]) if (v != par) {
        for (int j = 1; j <= v; ++j) {
            dp[v][j] = max(dp[u][j], dp[u][j - 1] + s);
        }
        dfs(v, u);
    }
}
void calc(int u) {
    for (int i = 1; i <= n; ++i)
        fill(dp[u], dp[u] + v + 1, 0);
    dfs(u, 0);
}

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);
    }

    if (n <= 1000) {
        for (int i = 1; i <= n; ++i) calc(i);
    }
    else calc(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
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4035 ms 52140 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 2676 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Incorrect 1 ms 2636 KB Output isn't correct
4 Halted 0 ms 0 KB -