oj.uz

Submission #578556

# Submission time Handle Problem Language Result Execution time Memory
578556 2022-06-17T09:19:21 Z andrei_boaca Chase (CEOI17_chase) C++14
40 / 100
 254 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int need=2;
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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 495800 KB Output is correct
2 Correct 227 ms 495876 KB Output is correct
3 Correct 218 ms 495856 KB Output is correct
4 Correct 239 ms 495984 KB Output is correct
5 Correct 244 ms 495848 KB Output is correct
6 Correct 217 ms 495832 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 495800 KB Output is correct
2 Correct 227 ms 495876 KB Output is correct
3 Correct 218 ms 495856 KB Output is correct
4 Correct 239 ms 495984 KB Output is correct
5 Correct 244 ms 495848 KB Output is correct
6 Correct 217 ms 495832 KB Output is correct
7 Correct 243 ms 500504 KB Output is correct
8 Correct 254 ms 496908 KB Output is correct
9 Correct 224 ms 496684 KB Output is correct
10 Correct 243 ms 500184 KB Output is correct
11 Correct 216 ms 497764 KB Output is correct
12 Correct 230 ms 496936 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 243 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 249 ms 495800 KB Output is correct
2 Correct 227 ms 495876 KB Output is correct
3 Correct 218 ms 495856 KB Output is correct
4 Correct 239 ms 495984 KB Output is correct
5 Correct 244 ms 495848 KB Output is correct
6 Correct 217 ms 495832 KB Output is correct
7 Correct 243 ms 500504 KB Output is correct
8 Correct 254 ms 496908 KB Output is correct
9 Correct 224 ms 496684 KB Output is correct
10 Correct 243 ms 500184 KB Output is correct
11 Correct 216 ms 497764 KB Output is correct
12 Correct 230 ms 496936 KB Output is correct
13 Runtime error 243 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -