oj.uz

Submission #511954

# Submission time Handle Problem Language Result Execution time Memory
511954 2022-01-16T05:33:30 Z Monarchuwu Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 131556 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 (đi vào subtree)
void dfs_1(int u, int par) {
    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] });
        }
    }
}
ll dp2[N][K];   // dp2[u][j]: bắt đầu tại u, sẽ dùng j lượt (đi lên root)
ll tmp[K];
void dfs_2(int u, int par) {
    for (int v : g[u]) if (v != par) {
        copy(dp2[u], dp2[u] + V + 1, tmp);

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

        for (int j = 1; j <= V; ++j) {
            dp2[v][j] = max({ dp2[v][j], tmp[j], tmp[j - 1] + sum_p[u] - p[v] });
        }

        dfs_2(v, 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];

    dfs_1(1, 0);
    dfs_2(1, 0);
    ll ans(0);
    for (int u = 1; u <= n; ++u) {
        ans = max({ ans, dp1[u][V], dp2[u][V] });
        for (int j = 0; j < V; ++j) {
            ans = max(ans, max(dp1[u][j], dp2[u][j]) + sum_p[u]);
        }
    }
    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 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 1 ms 2676 KB Output is correct
6 Correct 2 ms 2684 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 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 1 ms 2676 KB Output is correct
6 Correct 2 ms 2684 KB Output is correct
7 Correct 4 ms 3916 KB Output is correct
8 Correct 3 ms 3916 KB Output is correct
9 Correct 13 ms 3444 KB Output is correct
10 Correct 3 ms 4172 KB Output is correct
11 Correct 3 ms 4172 KB Output is correct
12 Correct 3 ms 4084 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 131504 KB Output is correct
2 Correct 233 ms 131556 KB Output is correct
3 Execution timed out 4010 ms 7876 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 1 ms 2676 KB Output is correct
6 Correct 2 ms 2684 KB Output is correct
7 Correct 4 ms 3916 KB Output is correct
8 Correct 3 ms 3916 KB Output is correct
9 Correct 13 ms 3444 KB Output is correct
10 Correct 3 ms 4172 KB Output is correct
11 Correct 3 ms 4172 KB Output is correct
12 Correct 3 ms 4084 KB Output is correct
13 Correct 218 ms 131504 KB Output is correct
14 Correct 233 ms 131556 KB Output is correct
15 Execution timed out 4010 ms 7876 KB Time limit exceeded
16 Halted 0 ms 0 KB -