oj.uz

Submission #578531

# Submission time Handle Problem Language Result Execution time Memory
578531 2022-06-17T08:05:36 Z andrei_boaca Chase (CEOI17_chase) C++14
40 / 100
 4000 ms 94924 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,s[100005];
ll MAXROOT=1;
bool use[100005];
void dfs(int nod)
{
    for(int i=1;i<=v;i++)
        dp[nod][i]=0;
    ll suma=0;
    int cnt=0;
    for(int i:muchii[nod])
        if(i!=par[nod])
        {
            suma+=p[i];
            par[i]=nod;
            cnt++;
            dfs(i);
        }
    s[nod]=suma;
    for(int j=1;j<=v;j++)
    {
        dp[nod][j]=dp[nod][j-1];
        for(int i:muchii[nod])
            if(i!=par[nod])
            {
                dp[nod][j]=max(dp[nod][j],dp[i][j]);
                dp[nod][j]=max(dp[nod][j],dp[i][j-1]+s[nod]);
            }
    }
}
void reroot(int nod,int fiu)
{
    s[nod]-=p[fiu];
    s[fiu]+=p[nod];
    par[nod]=fiu;
    par[fiu]=0;
    for(int j=1;j<=v;j++)
    {
        dp[nod][j]=dp[nod][j-1];
        for(int i:muchii[nod])
            if(i!=par[nod])
            {
                dp[nod][j]=max(dp[nod][j],dp[i][j]);
                dp[nod][j]=max(dp[nod][j],dp[i][j-1]+s[nod]);
            }
    }
    for(int j=1;j<=v;j++)
    {
        dp[fiu][j]=dp[fiu][j-1];
        for(int i:muchii[fiu])
            if(i!=par[fiu])
            {
                dp[fiu][j]=max(dp[fiu][j],dp[i][j]);
                dp[fiu][j]=max(dp[fiu][j],dp[i][j-1]+s[fiu]);
            }
    }
}
void calc(int nod)
{
    use[nod]=1;
    ans=max(ans,dp[nod][v]);
    for(int i:muchii[nod])
        if(i!=par[nod]&&!use[i])
        {
            reroot(nod,i);
            calc(i);
            reroot(i,nod);
        }
}
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);
    }
    dfs(1);
    calc(1);
    cout<<ans;
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 8 ms 3540 KB Output is correct
8 Correct 2 ms 3540 KB Output is correct
9 Correct 49 ms 3540 KB Output is correct
10 Correct 8 ms 3540 KB Output is correct
11 Correct 5 ms 3536 KB Output is correct
12 Correct 4 ms 3576 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 94924 KB Output is correct
2 Correct 728 ms 94920 KB Output is correct
3 Execution timed out 4058 ms 91060 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 8 ms 3540 KB Output is correct
8 Correct 2 ms 3540 KB Output is correct
9 Correct 49 ms 3540 KB Output is correct
10 Correct 8 ms 3540 KB Output is correct
11 Correct 5 ms 3536 KB Output is correct
12 Correct 4 ms 3576 KB Output is correct
13 Correct 721 ms 94924 KB Output is correct
14 Correct 728 ms 94920 KB Output is correct
15 Execution timed out 4058 ms 91060 KB Time limit exceeded
16 Halted 0 ms 0 KB -