oj.uz

Submission #802991

# Submission time Handle Problem Language Result Execution time Memory
802991 2023-08-02T17:31:36 Z PoonYaPat Chase (CEOI17_chase) C++14
100 / 100
 281 ms 222356 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,k;
ll val[100005],dp[100005][105][2],ans,sum[100005];
vector<int> adj[100005];

void dfs(int x, int par) {
    dp[x][1][1]=sum[x];
    for (auto s : adj[x]) {
        if (s==par) continue;
        dfs(s,x);
        for (int i=1; i<=k; ++i) {
            dp[x][i][0]=max({dp[x][i][0],dp[x][i-1][0],dp[s][i][0],dp[s][i-1][0]+sum[x]-val[par]});
            dp[x][i][1]=max({dp[x][i][1],dp[x][i-1][1],dp[s][i][1],dp[s][i-1][1]+sum[x]-val[s]});
        }
    }

    ll mmax[105];
    memset(mmax,0,sizeof(mmax));

    for (auto s : adj[x]) if (s!=par) {
        for (int i=0; i<=k; ++i) {
            ans=max(ans,dp[s][i][1]+mmax[k-i]); //dont use at x
            if (i!=k && i!=0) ans=max(ans,dp[s][i][1]+sum[x]-val[s]+mmax[k-i-1]); //use at x in the middle
        }
        for (int i=0; i<=k; ++i) mmax[i]=max(mmax[i],dp[s][i][0]);
    }

    memset(mmax,0,sizeof(mmax));
    reverse(adj[x].begin(),adj[x].end());

    for (auto s : adj[x]) if (s!=par)  {
        for (int i=0; i<=k; ++i) {
            ans=max(ans,dp[s][i][1]+mmax[k-i]); //dont use at x
            if (i!=k && i!=0) ans=max(ans,dp[s][i][1]+sum[x]-val[s]+mmax[k-i-1]); //use at x in the middle
        }
        for (int i=0; i<=k; ++i) mmax[i]=max(mmax[i],dp[s][i][0]);
    }
    if (k) ans=max(ans,mmax[k-1]+sum[x]); //use x as a start point
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k;
    for (int i=1; i<=n; ++i) cin>>val[i];
    for (int i=0; i<n-1; ++i) {
        int a,b; cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i=1; i<=n; ++i) {
        for (auto s : adj[i]) sum[i]+=val[s];
    }
    dfs(1,0);
    cout<<ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2680 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2680 KB Output is correct
7 Correct 4 ms 4756 KB Output is correct
8 Correct 3 ms 4820 KB Output is correct
9 Correct 2 ms 4308 KB Output is correct
10 Correct 3 ms 4308 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct
12 Correct 2 ms 4308 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 220444 KB Output is correct
2 Correct 248 ms 221788 KB Output is correct
3 Correct 262 ms 174184 KB Output is correct
4 Correct 111 ms 173852 KB Output is correct
5 Correct 262 ms 174156 KB Output is correct
6 Correct 281 ms 173900 KB Output is correct
7 Correct 246 ms 173928 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2680 KB Output is correct
7 Correct 4 ms 4756 KB Output is correct
8 Correct 3 ms 4820 KB Output is correct
9 Correct 2 ms 4308 KB Output is correct
10 Correct 3 ms 4308 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct
12 Correct 2 ms 4308 KB Output is correct
13 Correct 260 ms 220444 KB Output is correct
14 Correct 248 ms 221788 KB Output is correct
15 Correct 262 ms 174184 KB Output is correct
16 Correct 111 ms 173852 KB Output is correct
17 Correct 262 ms 174156 KB Output is correct
18 Correct 281 ms 173900 KB Output is correct
19 Correct 246 ms 173928 KB Output is correct
20 Correct 255 ms 173828 KB Output is correct
21 Correct 109 ms 173952 KB Output is correct
22 Correct 252 ms 173924 KB Output is correct
23 Correct 113 ms 173924 KB Output is correct
24 Correct 247 ms 173896 KB Output is correct
25 Correct 257 ms 173808 KB Output is correct
26 Correct 271 ms 222356 KB Output is correct
27 Correct 258 ms 222328 KB Output is correct