oj.uz

Submission #578533

# Submission time Handle Problem Language Result Execution time Memory
578533 2022-06-17T08:11:47 Z andrei_boaca Chase (CEOI17_chase) C++14
40 / 100
 262 ms 524288 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];
multiset<ll> vals[100005][105];
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);
            for(int j=1;j<=v;j++)
                vals[nod][j].insert(dp[i][j]);
        }
    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 calcdp(int nod,int j)
{
    dp[nod][j]=0;
    if(vals[nod][j].empty())
        return;
    ll x=*prev(vals[nod][j].end());
    ll y=s[nod];
    if(j>1)
        y=*prev(vals[nod][j-1].end())+s[nod];
    dp[nod][j]=max(x,y);
}
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++)
        vals[nod][j].erase(vals[nod][j].find(dp[fiu][j]));
    for(int j=1;j<=v;j++)
        calcdp(nod,j);
    for(int j=1;j<=v;j++)
        vals[fiu][j].insert(dp[nod][j]);
    for(int j=1;j<=v;j++)
        calcdp(fiu,j);
}
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 224 ms 495772 KB Output is correct
2 Correct 217 ms 495840 KB Output is correct
3 Correct 235 ms 495812 KB Output is correct
4 Correct 251 ms 495856 KB Output is correct
5 Correct 235 ms 495804 KB Output is correct
6 Correct 208 ms 495928 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 495772 KB Output is correct
2 Correct 217 ms 495840 KB Output is correct
3 Correct 235 ms 495812 KB Output is correct
4 Correct 251 ms 495856 KB Output is correct
5 Correct 235 ms 495804 KB Output is correct
6 Correct 208 ms 495928 KB Output is correct
7 Correct 262 ms 501452 KB Output is correct
8 Correct 236 ms 497048 KB Output is correct
9 Correct 228 ms 497064 KB Output is correct
10 Correct 243 ms 501324 KB Output is correct
11 Correct 241 ms 498128 KB Output is correct
12 Correct 241 ms 497164 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 224 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 495772 KB Output is correct
2 Correct 217 ms 495840 KB Output is correct
3 Correct 235 ms 495812 KB Output is correct
4 Correct 251 ms 495856 KB Output is correct
5 Correct 235 ms 495804 KB Output is correct
6 Correct 208 ms 495928 KB Output is correct
7 Correct 262 ms 501452 KB Output is correct
8 Correct 236 ms 497048 KB Output is correct
9 Correct 228 ms 497064 KB Output is correct
10 Correct 243 ms 501324 KB Output is correct
11 Correct 241 ms 498128 KB Output is correct
12 Correct 241 ms 497164 KB Output is correct
13 Runtime error 224 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -