oj.uz

Submission #874142

# Submission time Handle Problem Language Result Execution time Memory
874142 2023-11-16T10:33:25 Z josanneo22 Chase (CEOI17_chase) C++17
100 / 100
 285 ms 206096 KB 
/*
Problem: P4657 [CEOI2017] Chase
When:    2023-11-16 14:54:19
Author:  Ning07
*/

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)

const int N=2e5+600;
i64 n,V,a[N],head[N<<1],ver[N<<1],nxt[N<<1],tot=0,tmp[N];
i64 ans=0,dp[N][120][2],sum[N];
void add_edge(int x,int y){
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
void update(int nw,int son,int fa){
    L(i,1,V-1) ans=max(ans,dp[nw][i][0]+dp[son][V-i][1]);
    L(i,1,V){
        dp[nw][i][0]=max({dp[nw][i][0],dp[son][i][0],dp[son][i-1][0]+sum[nw]-a[son]});
        dp[nw][i][1]=max({dp[nw][i][1],dp[son][i][1],dp[son][i-1][1]+sum[nw]-a[fa]});
    }
}
void dfs(int u,int f){
    for(int i=head[u];i;i=nxt[i]){
        int v=ver[i];
        if(v==f) continue;
        dfs(v,u);
    }
    int cnt=0;
    L(i,1,V) dp[u][i][0]=sum[u];
    for(int i=head[u];i;i=nxt[i]){
        int v=ver[i];
        update(u,v,f);
        tmp[++cnt]=v;
    }
    L(i,1,V) dp[u][i][0]=sum[u],dp[u][i][1]=0;
    R(i,cnt,1) update(u,tmp[i],f);
    ans=max({ans,dp[u][V][0],dp[u][V][1]});
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    std::cin>>n>>V;
    L(i,1,n) std::cin>>a[i];
    L(i,1,n-1){
        int u,v; 
        std::cin>>u>>v;
        add_edge(u,v);
        add_edge(v,u);
    }
    L(i,1,n){
        for(int j=head[i];j;j=nxt[j]){
            int v=ver[j];
            sum[i]+=a[v];
        }
    }
    dfs(1,0);
    cout<<ans<<'\n';
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 205036 KB Output is correct
2 Correct 245 ms 206072 KB Output is correct
3 Correct 236 ms 202236 KB Output is correct
4 Correct 93 ms 203344 KB Output is correct
5 Correct 265 ms 201388 KB Output is correct
6 Correct 255 ms 201180 KB Output is correct
7 Correct 278 ms 201396 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 3 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 1 ms 7256 KB Output is correct
10 Correct 4 ms 7260 KB Output is correct
11 Correct 2 ms 7260 KB Output is correct
12 Correct 2 ms 7256 KB Output is correct
13 Correct 273 ms 205036 KB Output is correct
14 Correct 245 ms 206072 KB Output is correct
15 Correct 236 ms 202236 KB Output is correct
16 Correct 93 ms 203344 KB Output is correct
17 Correct 265 ms 201388 KB Output is correct
18 Correct 255 ms 201180 KB Output is correct
19 Correct 278 ms 201396 KB Output is correct
20 Correct 257 ms 201216 KB Output is correct
21 Correct 29 ms 14256 KB Output is correct
22 Correct 260 ms 201428 KB Output is correct
23 Correct 99 ms 203328 KB Output is correct
24 Correct 285 ms 201300 KB Output is correct
25 Correct 214 ms 201812 KB Output is correct
26 Correct 252 ms 206096 KB Output is correct
27 Correct 255 ms 205908 KB Output is correct