oj.uz

Submission #870383

# Submission time Handle Problem Language Result Execution time Memory
870383 2023-11-07T14:29:06 Z fanwen Chase (CEOI17_chase) C++17
100 / 100
 188 ms 161876 KB 
#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }
template <class T> T max(T a, T b, T c) { return max(a, max(b, c)); }

const int MAX = 1e5 + 5;

int N, K, p[MAX];
long long ans, sum_adj[MAX], up[MAX][105], down[MAX][105];
vector <int> adj[MAX];

void dfs(int u, int pa) {
    up[u][1] = sum_adj[u];
    for (auto v : adj[u]) if(v != pa) {
        dfs(v, u);
        FOR(i, 1, K) ans = max(ans, up[u][i] + down[v][K - i]);
        FOR(i, 1, K) {
            down[u][i] = max(down[u][i], down[v][i], down[v][i - 1] + sum_adj[u] - p[pa]);
            up[u][i] = max(up[u][i], up[v][i], up[v][i - 1] + sum_adj[u]- p[v]);
        }
    }

    memset(up[u], 0, sizeof up[u]);
    up[u][1] = sum_adj[u];

    reverse(adj[u].begin(), adj[u].end());

    for (auto v : adj[u]) if(v != pa) {
        FOR(i, 1, K) ans = max(ans, up[u][i] + down[v][K - i]);
        FOR(i, 1, K) {
            down[u][i] = max(down[u][i], down[v][i], down[v][i - 1] + sum_adj[u] - p[pa]);
            up[u][i] = max(up[u][i], up[v][i], up[v][i - 1] + sum_adj[u]- p[v]);
        }
    } 
}

void you_make_it(void) {
    cin >> N >> K;
    FOR(i, 1, N) cin >> p[i];
    FORE(i, 1, N) {
        int u, v; cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
        sum_adj[u] += p[v], sum_adj[v] += p[u];
    }
    dfs(1, 0);
    cout << ans;
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("ceoi17_chase");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:13:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
chase.cpp:69:5: note: in expansion of macro 'file'
   69 |     file("ceoi17_chase");
      |     ^~~~
chase.cpp:13:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
chase.cpp:69:5: note: in expansion of macro 'file'
   69 |     file("ceoi17_chase");
      |     ^~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 3 ms 6744 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 138068 KB Output is correct
2 Correct 147 ms 138068 KB Output is correct
3 Correct 134 ms 94048 KB Output is correct
4 Correct 106 ms 159784 KB Output is correct
5 Correct 185 ms 161708 KB Output is correct
6 Correct 177 ms 161688 KB Output is correct
7 Correct 178 ms 161652 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 3 ms 6744 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 155 ms 138068 KB Output is correct
14 Correct 147 ms 138068 KB Output is correct
15 Correct 134 ms 94048 KB Output is correct
16 Correct 106 ms 159784 KB Output is correct
17 Correct 185 ms 161708 KB Output is correct
18 Correct 177 ms 161688 KB Output is correct
19 Correct 178 ms 161652 KB Output is correct
20 Correct 182 ms 161876 KB Output is correct
21 Correct 68 ms 93608 KB Output is correct
22 Correct 188 ms 161740 KB Output is correct
23 Correct 106 ms 159560 KB Output is correct
24 Correct 183 ms 161872 KB Output is correct
25 Correct 127 ms 93628 KB Output is correct
26 Correct 158 ms 138324 KB Output is correct
27 Correct 153 ms 138328 KB Output is correct