oj.uz

Submission #672556

# Submission time Handle Problem Language Result Execution time Memory
672556 2022-12-16T15:56:14 Z MohamedFaresNebili Chase (CEOI17_chase) C++14
100 / 100
 308 ms 173648 KB 
#include <bits/stdc++.h>

            using namespace std;
            using ll = long long;

            #define int ll

            int res, N, K, P[100005];
            int X[100001][101], Y[100001][101];
            vector<int> adj[100005];

            void dfs(int v, int p) {
                int S = 0;
                for(auto u : adj[v]) S += P[u];
                X[v][1] = S;
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    dfs(u, v);
                    for(int i = 1; i <= K; i++) {
                        res = max(res, X[v][i] + Y[u][K - i]);
                        X[v][i] = max({X[v][i], X[v][i - 1], X[u][i], X[u][i - 1] + S - P[u]});
                        Y[v][i] = max({Y[v][i], Y[v][i - 1], Y[u][i], Y[u][i - 1] + S - P[p]});
                    }
                }

                reverse(adj[v].begin(), adj[v].end());
                memset(X[v], 0, sizeof X[v]);
                memset(Y[v], 0, sizeof Y[v]);
                X[v][1] = S;
                for(auto u : adj[v]) {
                    if(u == p) continue;
                    for(int i = 1; i <= K; i++) {
                        res = max(res, X[v][i] + Y[u][K - i]);
                        X[v][i] = max({X[v][i], X[v][i - 1], X[u][i], X[u][i - 1] + S - P[u]});
                        Y[v][i] = max({Y[v][i], Y[v][i - 1], Y[u][i], Y[u][i - 1] + S - P[p]});
                    }
                }
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> K;
                for(int l = 1; l <= N; l++)
                    cin >> P[l];
                for(int l = 0; l < N - 1; l++) {
                    int U, V; cin >> U >> V;
                    adj[U].push_back(V);
                    adj[V].push_back(U);
                }
                dfs(1, 0);
                cout << res << "\n";
                return 0;
            }

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2680 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2680 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 4 ms 4364 KB Output is correct
8 Correct 3 ms 4352 KB Output is correct
9 Correct 3 ms 4308 KB Output is correct
10 Correct 5 ms 4228 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct
12 Correct 3 ms 4224 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 173548 KB Output is correct
2 Correct 245 ms 173504 KB Output is correct
3 Correct 248 ms 167552 KB Output is correct
4 Correct 149 ms 167284 KB Output is correct
5 Correct 308 ms 167376 KB Output is correct
6 Correct 266 ms 167420 KB Output is correct
7 Correct 269 ms 167396 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2680 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 4 ms 4364 KB Output is correct
8 Correct 3 ms 4352 KB Output is correct
9 Correct 3 ms 4308 KB Output is correct
10 Correct 5 ms 4228 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct
12 Correct 3 ms 4224 KB Output is correct
13 Correct 255 ms 173548 KB Output is correct
14 Correct 245 ms 173504 KB Output is correct
15 Correct 248 ms 167552 KB Output is correct
16 Correct 149 ms 167284 KB Output is correct
17 Correct 308 ms 167376 KB Output is correct
18 Correct 266 ms 167420 KB Output is correct
19 Correct 269 ms 167396 KB Output is correct
20 Correct 259 ms 167380 KB Output is correct
21 Correct 145 ms 167372 KB Output is correct
22 Correct 266 ms 167392 KB Output is correct
23 Correct 150 ms 167324 KB Output is correct
24 Correct 277 ms 167500 KB Output is correct
25 Correct 226 ms 167240 KB Output is correct
26 Correct 265 ms 173620 KB Output is correct
27 Correct 265 ms 173648 KB Output is correct