oj.uz

Submission #578505

# Submission time Handle Problem Language Result Execution time Memory
578505 2022-06-17T06:59:40 Z andrei_boaca Chase (CEOI17_chase) C++14
0 / 100
 152 ms 96144 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n,v,p[100005],par[100005],dp[100005][105];
vector<ll> muchii[100005];
ll ans=0;
ll MAXROOT=1;
void dfs(int nod)
{
    for(int i=1;i<=v;i++)
        dp[nod][i]=0;
    ll suma=p[nod];
    for(int i:muchii[nod])
        if(i!=par[nod])
        {
            suma+=p[i];
            par[i]=nod;
            dfs(i);
        }
    dp[nod][1]=suma;
    for(int j=2;j<=v;j++)
    {
        dp[nod][j]=dp[nod][j-1];
        for(int i:muchii[nod])
            if(i!=par[nod])
            {
                ll val=dp[i][j-1]+suma-p[i];
                dp[nod][j]=max(dp[nod][j],val);
            }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>v;
    for(int i=1;i<=n;i++)
        cin>>p[i];
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }
    if(n<=1000)
        MAXROOT=n;
    for(int root=1;root<=MAXROOT;root++)
    {
        for(int i=1;i<=n;i++)
            par[i]=0;
        dfs(root);
        ans=max(ans,dp[root][v]-p[root]);
    }
    cout<<ans;
    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2692 KB Output is correct
2 Incorrect 1 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2692 KB Output is correct
2 Incorrect 1 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2692 KB Output is correct
2 Incorrect 1 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -