oj.uz

Submission #210081

# Submission time Handle Problem Language Result Execution time Memory
210081 2020-03-16T14:14:55 Z arjun_9426 Chase (CEOI17_chase) C++17
0 / 100
 162 ms 96248 KB 
// code written by Arjun Tomar
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int> 
#define pll pair<ll,ll>
#define mp(x,y) make_pair(x,y)
const ll inf=1e18;
const int nax=1e5+5;
const int gax=101;
vector<vector<int>> v(nax);
int vis[nax]={0};
map<int,vector<ll>> m[nax];

ll a[nax];
vector<vector<ll>> dp(nax,vector<ll>(gax,0));

void dfs(int ci){
    vis[ci]=1;
    ll g=a[ci];
    for(auto x : v[ci]){
        if(vis[x]==0) g+=a[x];
    }
    for(int i=1;i<gax;i++) dp[ci][i]=g;
    for(auto x : v[ci]){
        if(vis[x]==1) continue;
        dfs(x);
        for(int i=1;i<gax-1;i++){
            dp[ci][i+1]=max(dp[ci][i+1],dp[x][i]+dp[ci][1]-a[x]);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,r;
    cin>>n>>r;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n-1;i++){
        int x,y;cin>>x>>y;
        x--; y--;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(0);
    ll ans=-inf;
    for(int j=1;j<=r;j++){
        ans=max(dp[0][j]-a[0],ans);
    }
    cout<<ans<<'\n';
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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