oj.uz

Submission #618855

# Submission time Handle Problem Language Result Execution time Memory
618855 2022-08-02T07:58:06 Z nghiass001 Chase (CEOI17_chase) C++17
0 / 100
 196 ms 182000 KB 
#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)
#define REP(i, l, r) for(int i = (l); i < (r); ++i)
#define REPD(i, r, l) for(int i = (r) - 1; i >= (l); --i)
using namespace std;
const int N = 1e5 + 5, M = 105;
int n, m, a[N];
long long res, sum[N], dp[N][M], dp2[N][M]; /// bottom-up / top-down
vector<int> S[N];

void Enter() {
    cin >> n >> m;
    FOR(i, 1, n) cin >> a[i];
    REP(i, 1, n) {
        int u, v;
        cin >> u >> v;
        S[u].push_back(v);
        S[v].push_back(u);
    }
}

void DFS(int u, int p) {
    sum[u] = a[u] + a[p];
    for(int v : S[u]) if (v != p) {
        DFS(v, u);
        sum[u] += a[v];
    }
    dp[u][1] = sum[u] - a[u];
    dp2[u][1] = sum[u];
    for(int v : S[u]) if (v != p) {
        REP(i, 1, m) {
            res = max(res, dp[u][i] + dp2[v][m - i] - a[u] - a[v]);
            res = max(res, dp2[u][i] + dp[v][m - i] - a[u] - a[v]);
        }
        REP(i, 0, m) {
            if (i) dp[u][i + 1] = max(dp[u][i + 1], dp[v][i] + sum[u] - a[u] - a[v]);
            dp2[u][i + 1] = max(dp2[u][i + 1], dp2[v][i] - a[u] - a[v]);
        }
    }
    res = max(res, dp[u][m]);
    res = max(res, dp2[u][m] - a[u]);
}

void Process() {
    DFS(1, 0);
    cout << res;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    if (fopen("chase.inp", "r")) freopen("chase.inp", "r", stdin);
    Enter();
    Process();
}

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:53:41: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     if (fopen("chase.inp", "r")) freopen("chase.inp", "r", stdin);
      |                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 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 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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