oj.uz

Submission #1028403

# Submission time Handle Problem Language Result Execution time Memory
1028403 2024-07-19T19:17:16 Z vjudge1 Chase (CEOI17_chase) C++17
30 / 100
 275 ms 264020 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define deb(x) ;
using lli=long long int;
using ld=long double;

vector<vector<lli>> dp;
vector<vector<lli>> dp1;
vector<vector<lli>> dp2;
vector<lli> pajaro;
vector<vector<lli>> adj;
vector<vector<lli>> sons;
vector<lli> par;
lli v; 
lli ans=0;

void dfs(lli x, lli p){
    deb(x);
    deb(p);
    for(lli y: adj[x]){
        if(y==p) continue;
        dfs(y,x);
        par[y]=x;
        sons[x].pb(y);

    }
}

void echaleganas(lli x){
    
    for(lli y: sons[x]){
        echaleganas(y);
    
    }
    lli sum=0;
/*
    //Le echo pan
    
    for(lli y: sons[x]){
        sum+=pajaro[y];
        for(lli i=v; i>=0; --i){
            for(lli j=v-1; j>=0; --j){
                dp1[x][i]=max(dp1[x][i], dp1[x][j]+dp[y][i-j]);
            }
        }
    }
    for(lli i=1; i<=v; ++i){
        dp1[x][i]=dp1[x][i-1];
    }
    for(lli i=1; i<=v; ++i){
        dp1[x][i]+=sum;
    }
    ans=max(ans, dp1[x][v]+pajaro[par[x]]);

    //No le hecho pan

     for(lli y: sons[x]){
       // sum+=pajaro[y];
        for(lli i=v; i>=0; --i){
            for(lli j=v-1; j>=0; --j){
                dp2[x][i]=max(dp2[x][i], dp2[x][j]+dp[y][i-j]);
            }
        }
    }
    ans=max(ans, dp2[x][v]); */
    for(lli i=0; i<=v; ++i){
        dp1[x][i]=0;
        dp2[x][i]=0;
    }    
     for(lli y: sons[x]){
        sum+=pajaro[y];
        for(lli i=v; i>0; --i){
            dp1[x][i]=max(dp1[x][i],dp[y][i-1] );
        }
    }

    for(lli i=1; i<=v; ++i){
        dp1[x][i]+=sum;
    }
      for(lli y: sons[x]){
       // sum+=pajaro[y];
        for(lli i=v; i>=0; --i){
                dp2[x][i]=max(dp2[x][i], dp[y][i]);
        }
    }
    deb("_____________________-");
    deb(x);
    for(lli i=0; i<=v; ++i){
    
        dp[x][i]=max(dp1[x][i], dp2[x][i]);
        deb(dp1[x][i]);
        deb(dp2[x][i]);
        deb(dp[x][i]);
    }

}

void solve(){
    lli n;
    cin>>n>>v;

    dp1.resize(n, vector<lli> (v+1));
    dp2.resize(n, vector<lli> (v+1));
    dp.resize(n, vector<lli> (v+1));
    pajaro.resize(n);
    for(lli i=0; i<n; ++i){
        cin>>pajaro[i];
    }
    adj.resize(n);
    sons.resize(n);
    par.resize(n);
    for(lli i=0; i<n-1; ++i){
        lli a,b;
        cin>>a>>b;
        a--;b--;
      
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(0,-1);
    echaleganas(0);
    ans=dp[0][v];
    cout<<ans<<endl;


}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    lli t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 264020 KB Output is correct
2 Correct 212 ms 263900 KB Output is correct
3 Correct 179 ms 259780 KB Output is correct
4 Correct 71 ms 30036 KB Output is correct
5 Correct 251 ms 260180 KB Output is correct
6 Correct 275 ms 259948 KB Output is correct
7 Correct 251 ms 260144 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -