oj.uz

Submission #882887

# Submission time Handle Problem Language Result Execution time Memory
882887 2023-12-04T04:25:08 Z josanneo22 Chase (CEOI17_chase) C++17
100 / 100
 284 ms 201616 KB 
#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],tmp[N];
i64 ans=0,dp[N][120][2],sum[N];
const int MN=2e5;
int head[MN<<1],ver[MN<<1],nxt[MN<<1],tot=0;
void add_edge(int x,int y){
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
#define trav(v,u) for(int j=head[u],v=ver[j];j;j=nxt[j],v=ver[j])
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){
    trav(v,u){
        if(v==f) continue;
        dfs(v,u);
    }
    int cnt=0;
    L(i,1,V) dp[u][i][0]=sum[u];
    trav(v,u){
        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){
    	trav(v,i){
            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 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 201492 KB Output is correct
2 Correct 246 ms 201556 KB Output is correct
3 Correct 235 ms 198116 KB Output is correct
4 Correct 110 ms 199020 KB Output is correct
5 Correct 260 ms 196844 KB Output is correct
6 Correct 262 ms 197120 KB Output is correct
7 Correct 260 ms 196752 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 3 ms 6748 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 1 ms 6748 KB Output is correct
13 Correct 253 ms 201492 KB Output is correct
14 Correct 246 ms 201556 KB Output is correct
15 Correct 235 ms 198116 KB Output is correct
16 Correct 110 ms 199020 KB Output is correct
17 Correct 260 ms 196844 KB Output is correct
18 Correct 262 ms 197120 KB Output is correct
19 Correct 260 ms 196752 KB Output is correct
20 Correct 259 ms 196904 KB Output is correct
21 Correct 27 ms 10332 KB Output is correct
22 Correct 259 ms 196916 KB Output is correct
23 Correct 96 ms 198972 KB Output is correct
24 Correct 284 ms 196872 KB Output is correct
25 Correct 207 ms 197200 KB Output is correct
26 Correct 243 ms 201616 KB Output is correct
27 Correct 258 ms 201480 KB Output is correct