oj.uz

Submission #511668

# Submission time Handle Problem Language Result Execution time Memory
511668 2022-01-16T03:43:28 Z Monarchuwu Chase (CEOI17_chase) C++17
70 / 100
 1055 ms 90760 KB 
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;

#include<chrono>
#include<random>
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

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

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

    for (int v : g[u]) if (v != par) {
        dp[v][0] = 0;
        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) {
    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);
        for (int i = 0; i < 20; ++i)
            calc(rd() % (n - 1) + 2);
    }
    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 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2608 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 1 ms 2636 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2608 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 1 ms 2636 KB Output is correct
7 Correct 232 ms 3540 KB Output is correct
8 Correct 28 ms 3556 KB Output is correct
9 Correct 25 ms 3524 KB Output is correct
10 Correct 223 ms 3500 KB Output is correct
11 Correct 83 ms 3404 KB Output is correct
12 Correct 36 ms 3500 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 90736 KB Output is correct
2 Correct 860 ms 90760 KB Output is correct
3 Correct 522 ms 86308 KB Output is correct
4 Correct 260 ms 86132 KB Output is correct
5 Correct 1029 ms 86212 KB Output is correct
6 Correct 1040 ms 86136 KB Output is correct
7 Correct 998 ms 86220 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2608 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 1 ms 2636 KB Output is correct
7 Correct 232 ms 3540 KB Output is correct
8 Correct 28 ms 3556 KB Output is correct
9 Correct 25 ms 3524 KB Output is correct
10 Correct 223 ms 3500 KB Output is correct
11 Correct 83 ms 3404 KB Output is correct
12 Correct 36 ms 3500 KB Output is correct
13 Correct 869 ms 90736 KB Output is correct
14 Correct 860 ms 90760 KB Output is correct
15 Correct 522 ms 86308 KB Output is correct
16 Correct 260 ms 86132 KB Output is correct
17 Correct 1029 ms 86212 KB Output is correct
18 Correct 1040 ms 86136 KB Output is correct
19 Correct 998 ms 86220 KB Output is correct
20 Incorrect 1055 ms 86132 KB Output isn't correct
21 Halted 0 ms 0 KB -