oj.uz

Submission #698370

# Submission time Handle Problem Language Result Execution time Memory
698370 2023-02-13T10:07:40 Z sugartheanh Chase (CEOI17_chase) C++14
30 / 100
 222 ms 156428 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]});
                    }
                }
 
               
            }
 
            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
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 133288 KB Output is correct
2 Correct 180 ms 133328 KB Output is correct
3 Correct 152 ms 88636 KB Output is correct
4 Correct 137 ms 154204 KB Output is correct
5 Correct 191 ms 156428 KB Output is correct
6 Correct 191 ms 156392 KB Output is correct
7 Correct 222 ms 156056 KB Output is correct

Subtask #4
0 / 30.0

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