oj.uz

Submission #1011551

# Submission time Handle Problem Language Result Execution time Memory
1011551 2024-06-30T15:16:45 Z NValchanov Chase (CEOI17_chase) C++17
100 / 100
 201 ms 189620 KB 
#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const int MAXK = 1e2 + 10;

int n, k;
vector < int > adj[MAXN];
ll c[MAXN];
ll ans;
ll dp[MAXN][MAXK][2];

void read()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        cin >> c[i];
    }
    for(int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

void dfs(int u, int par)
{
    ll sum = 0;
    for(int v : adj[u])
        sum += c[v];

    vector < int > nb;
    dp[u][1][1] = sum;

    for(int v : adj[u])
    {
        if(v == par)
            continue;

        dfs(v, u);

        nb.push_back(v);
        for(int i = 1; i <= k; i++)
        {
            ans = max(ans, dp[u][i][1] + dp[v][k - i][0]);
        }
        for(int i = 1; i <= k; i++)
        {
            dp[u][i][0] = max({dp[u][i][0], dp[v][i][0], dp[v][i - 1][0] + sum - c[par]});
            dp[u][i][1] = max({dp[u][i][1], dp[v][i][1], dp[v][i - 1][1] + sum - c[v]});
        }
    }

    /// after traversing children

    for(int i = 1; i <= k; i++)
    {
        dp[u][i][1] = 0;
    }

    dp[u][1][1] = sum;
    reverse(nb.begin(), nb.end());

    for(int v : nb)
    {
        for(int i = 1; i <= k; i++)
        {
            ans = max(ans, dp[u][i][1] + dp[v][k - i][0]);
        }
        for(int i = 1; i <= k; i++)
        {
            dp[u][i][1] = max({dp[u][i][1], dp[v][i][1], dp[v][i - 1][1] + sum - c[v]});
        }
    }
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    read();
    dfs(1, 0);

    cout << ans << endl;

    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 189008 KB Output is correct
2 Correct 182 ms 189444 KB Output is correct
3 Correct 118 ms 181840 KB Output is correct
4 Correct 99 ms 181076 KB Output is correct
5 Correct 167 ms 181076 KB Output is correct
6 Correct 201 ms 181076 KB Output is correct
7 Correct 172 ms 181072 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 4 ms 4444 KB Output is correct
8 Correct 2 ms 4512 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 3 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct
13 Correct 160 ms 189008 KB Output is correct
14 Correct 182 ms 189444 KB Output is correct
15 Correct 118 ms 181840 KB Output is correct
16 Correct 99 ms 181076 KB Output is correct
17 Correct 167 ms 181076 KB Output is correct
18 Correct 201 ms 181076 KB Output is correct
19 Correct 172 ms 181072 KB Output is correct
20 Correct 167 ms 181020 KB Output is correct
21 Correct 104 ms 181076 KB Output is correct
22 Correct 182 ms 180888 KB Output is correct
23 Correct 101 ms 181072 KB Output is correct
24 Correct 178 ms 181072 KB Output is correct
25 Correct 120 ms 181500 KB Output is correct
26 Correct 169 ms 189444 KB Output is correct
27 Correct 174 ms 189620 KB Output is correct