oj.uz

Submission #341385

# Submission time Handle Problem Language Result Execution time Memory
341385 2020-12-29T15:36:47 Z phathnv Chase (CEOI17_chase) C++11
100 / 100
 492 ms 334152 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e5 + 1;
const int V = 101;
const ll INF = 1e18;

int n, k, a[N];
vector <int> adj[N];

ll s[N], dp0[N][V][2], dp1[N][V][2], res[N];

void readInput(){
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(int i = 1; i < n; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

void maximize(ll &x, const ll &y){
    if (x < y)
        x = y;
}

void dfs(int u, int p){
    for(int v : adj[u])
        if (v != p){
            s[u] += a[v];
            s[v] += a[u];
            dfs(v, u);
        }

    for(int i = 0; i <= k; i++)
        for(int mask = 0; mask < 2; mask++)
            dp0[u][i][mask] = dp1[u][i][mask] = -INF;
    for(int i = 0; i <= k; i++){
        dp0[u][i][0] = dp1[u][i][0] = 0;
        if (i > 0)
            dp0[u][i][1] = dp1[u][i][1] = s[u];
    }

    for(int v : adj[u])
        if (v != p){
            for(int i = 0; i <= k; i++){
                maximize(res[u], dp0[u][i][0] + dp1[v][k - i][0]);
                maximize(res[u], dp0[u][i][1] + dp1[v][k - i][0]);
                maximize(res[u], dp0[u][i][0] + dp1[v][k - i][1] - a[u]);
                maximize(res[u], dp0[u][i][1] + dp1[v][k - i][1] - a[u]);

                maximize(res[u], dp1[u][i][0] + dp0[v][k - i][0]);
                maximize(res[u], dp1[u][i][1] + dp0[v][k - i][0] - a[v]);
                maximize(res[u], dp1[u][i][0] + dp0[v][k - i][1]);
                maximize(res[u], dp1[u][i][1] + dp0[v][k - i][1] - a[v]);
            }

            for(int i = 0; i <= k; i++){
                maximize(dp0[u][i][0], dp0[v][i][0]);
                maximize(dp0[u][i][0], dp0[v][i][1]);
                maximize(dp1[u][i][0], dp1[v][i][0]);
                maximize(dp1[u][i][0], dp1[v][i][1] - a[u]);

                if (i > 0){
                    maximize(dp0[u][i][1], dp0[v][i - 1][0] + s[u] - a[v]);
                    maximize(dp0[u][i][1], dp0[v][i - 1][1] + s[u] - a[v]);
                    maximize(dp1[u][i][1], dp1[v][i - 1][0] + s[u]);
                    maximize(dp1[u][i][1], dp1[v][i - 1][1] + s[u] - a[u]);
                }
            }
        }

    maximize(res[u], dp0[u][k][0]);
    maximize(res[u], dp0[u][k][1]);
    maximize(res[u], dp1[u][k][0]);
    maximize(res[u], dp1[u][k][1]);
}

void solve(){
    if (k == 0){
        printf("0");
        return;
    }
    dfs(1, -1);

    printf("%I64lld", *max_element(res + 1, res + 1 + n));
}

int main(){
    readInput();
    solve();
    return 0;
}

Compilation message

chase.cpp: In function 'void readInput()':
chase.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
chase.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
chase.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 333988 KB Output is correct
2 Correct 453 ms 333844 KB Output is correct
3 Correct 419 ms 326756 KB Output is correct
4 Correct 284 ms 326252 KB Output is correct
5 Correct 483 ms 326252 KB Output is correct
6 Correct 479 ms 326252 KB Output is correct
7 Correct 486 ms 326252 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 6 ms 5996 KB Output is correct
8 Correct 5 ms 5996 KB Output is correct
9 Correct 4 ms 5868 KB Output is correct
10 Correct 6 ms 5996 KB Output is correct
11 Correct 5 ms 5868 KB Output is correct
12 Correct 5 ms 5868 KB Output is correct
13 Correct 475 ms 333988 KB Output is correct
14 Correct 453 ms 333844 KB Output is correct
15 Correct 419 ms 326756 KB Output is correct
16 Correct 284 ms 326252 KB Output is correct
17 Correct 483 ms 326252 KB Output is correct
18 Correct 479 ms 326252 KB Output is correct
19 Correct 486 ms 326252 KB Output is correct
20 Correct 492 ms 326380 KB Output is correct
21 Correct 62 ms 8556 KB Output is correct
22 Correct 485 ms 326264 KB Output is correct
23 Correct 273 ms 326164 KB Output is correct
24 Correct 473 ms 326252 KB Output is correct
25 Correct 420 ms 326348 KB Output is correct
26 Correct 446 ms 334060 KB Output is correct
27 Correct 451 ms 334152 KB Output is correct