oj.uz

Submission #899942

# Submission time Handle Problem Language Result Execution time Memory
899942 2024-01-07T10:32:30 Z alexdd Chase (CEOI17_chase) C++17
40 / 100
 508 ms 94036 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,rez;
int p[100005];
int dp[100005][105];
int aux[105];
int aux2[105];
vector<int> con[100005];
void dfs(int nod, int par)
{
    int sump=0;
    for(auto adj:con[nod])
    {
        if(adj!=par)
        {
            dfs(adj,nod);
            sump += p[adj];
        }
    }
    for(int i=0;i<=k;i++)
        dp[nod][i]=aux[i]=aux2[i]=0;
    dp[nod][1] = sump + p[par];
    for(auto adj:con[nod])
    {
        if(adj!=par)
        {
            for(int i=1;i<=k;i++)
            {
                dp[nod][i] = max(dp[nod][i], dp[adj][i]);
                dp[nod][i] = max(dp[nod][i], dp[adj][i-1] + sump + p[par] - p[adj]);
            }
        }
    }
    for(int i=1;i<=k;i++)
    {
        dp[nod][i] = max(dp[nod][i], dp[nod][i-1]);
        rez = max(rez, dp[nod][i]);
        //cout<<nod<<" "<<i<<"   "<<dp[nod][i]<<"\n";
    }
}
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>p[i];
    int a,b;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        con[a].push_back(b);
        con[b].push_back(a);
    }
    if(n<=1000)
    {
        for(int i=1;i<=n;i++)
            dfs(i,0);
    }
    else
        dfs(1,0);
    cout<<rez;
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 508 ms 4796 KB Output is correct
8 Correct 33 ms 4700 KB Output is correct
9 Correct 29 ms 4696 KB Output is correct
10 Correct 502 ms 4752 KB Output is correct
11 Correct 156 ms 4696 KB Output is correct
12 Correct 52 ms 4696 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 508 ms 4796 KB Output is correct
8 Correct 33 ms 4700 KB Output is correct
9 Correct 29 ms 4696 KB Output is correct
10 Correct 502 ms 4752 KB Output is correct
11 Correct 156 ms 4696 KB Output is correct
12 Correct 52 ms 4696 KB Output is correct
13 Incorrect 161 ms 94036 KB Output isn't correct
14 Halted 0 ms 0 KB -