Submission #578555

#	Time	Username	Problem	Language	Result	Execution time	Memory
578555		andrei_boaca	Chase (CEOI17_chase)	C++14	40 / 100	256 ms	524288 KiB

chase

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int need=3;
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++)
            {
                if(vals[nod][j].size()<need)
                    vals[nod][j].insert(dp[i][j]);
                else
                {
                    if(*vals[nod][j].begin()<dp[i][j])
                    {
                        vals[nod][j].erase(vals[nod][j].begin());
                        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++)
    {
        if(vals[nod][j].find(dp[fiu][j])!=vals[nod][j].end())
            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++)
    {
        if(vals[fiu][j].size()<need)
            vals[fiu][j].insert(dp[nod][j]);
        else
        {
            if(*vals[fiu][j].begin()<dp[nod][j])
            {
                vals[fiu][j].erase(vals[fiu][j].begin());
                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;
}

Compilation message (stderr)

chase.cpp: In function 'void dfs(int)':
chase.cpp:27:39: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |                 if(vals[nod][j].size()<need)
      |                    ~~~~~~~~~~~~~~~~~~~^~~~~
chase.cpp: In function 'void reroot(int, int)':
chase.cpp:77:31: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |         if(vals[fiu][j].size()<need)
      |            ~~~~~~~~~~~~~~~~~~~^~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30