oj.uz

Submission #835811

# Submission time Handle Problem Language Result Execution time Memory
835811 2023-08-23T20:49:18 Z elkernos Chase (CEOI17_chase) C++17
0 / 100
 272 ms 146080 KB 
// clang-format off
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
// template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef XOX
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; }
sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; }
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
struct { template <class T> operator T() { T x; cin >> x; return x; } } in;
#define endl '\n'
#define pb emplace_back
#define vt vector
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using i64 = long long;
// #define int long long
// clang-format on

void ckmax(int& a, int b) { a = max(a, b); }

int32_t main()
{
    int n = in, v = in;
    vector<int> c(n + 1);
    for(int i = 1; i <= n; i++) c[i] = in;
    vector<vector<int>> g(n + 1);
    vector<int> ile(n + 1);
    for(int i = 1; i < n; i++) {
        int a = in, b = in;
        g[a].emplace_back(b), g[b].emplace_back(a);
        ile[a] += c[b]; ile[b] += c[a];
    }
    int ans = 0;
    vector<vector<int>> dpup(n + 1, vector<int>(v + 1)), dpdown(n + 1, vector<int>(v + 1));
    function<void(int, int)> dfs = [&](int u, int p) {
        dpup[u][1] = ile[u];
        vector<int> przepisz_up(v + 1), przepisz_down(v + 1);
        for(int to : g[u]) {
            if(to == p) continue;
            dfs(to, u);
            for(int j = 1; j <= v; j++) {
                i64 dist_up = max(dpup[to][j], dpup[to][j - 1] + ile[u] - c[to]);
                i64 dist_down = max(dpdown[to][j], dpdown[to][j - 1] + ile[to] - c[u]);
                przepisz_up[j] = dist_up; przepisz_down[j] = dist_down;
                if(j != v) {
                    ckmax(ans, dpup[u][v - j] + dist_down);
                    ckmax(ans, dpdown[u][v - j] + dist_up);
                    ckmax(ans, dpdown[to][j] + ile[u]);
                }
            }
            for(int j = 1; j <= v; j++) {
                ckmax(dpup[u][j], przepisz_up[j]); ckmax(dpdown[u][j], przepisz_down[j]);
                ckmax(ans, dpup[u][j]);
            }
        }
    };
    if(v == 0) { cout << 0; exit(0); }
    dfs(1, 0); cout << ans << endl;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 272 ms 146080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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