oj.uz

Submission #578555

# Submission time Handle Problem Language Result Execution time Memory
578555 2022-06-17T09:18:41 Z andrei_boaca Chase (CEOI17_chase) C++14
40 / 100
 256 ms 524288 KB 
#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

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 243 ms 495852 KB Output is correct
2 Correct 209 ms 495832 KB Output is correct
3 Correct 210 ms 495908 KB Output is correct
4 Correct 213 ms 495744 KB Output is correct
5 Correct 227 ms 495756 KB Output is correct
6 Correct 239 ms 495728 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 495852 KB Output is correct
2 Correct 209 ms 495832 KB Output is correct
3 Correct 210 ms 495908 KB Output is correct
4 Correct 213 ms 495744 KB Output is correct
5 Correct 227 ms 495756 KB Output is correct
6 Correct 239 ms 495728 KB Output is correct
7 Correct 256 ms 501200 KB Output is correct
8 Correct 240 ms 496900 KB Output is correct
9 Correct 224 ms 496864 KB Output is correct
10 Correct 250 ms 500876 KB Output is correct
11 Correct 238 ms 497996 KB Output is correct
12 Correct 225 ms 497224 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 225 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 243 ms 495852 KB Output is correct
2 Correct 209 ms 495832 KB Output is correct
3 Correct 210 ms 495908 KB Output is correct
4 Correct 213 ms 495744 KB Output is correct
5 Correct 227 ms 495756 KB Output is correct
6 Correct 239 ms 495728 KB Output is correct
7 Correct 256 ms 501200 KB Output is correct
8 Correct 240 ms 496900 KB Output is correct
9 Correct 224 ms 496864 KB Output is correct
10 Correct 250 ms 500876 KB Output is correct
11 Correct 238 ms 497996 KB Output is correct
12 Correct 225 ms 497224 KB Output is correct
13 Runtime error 225 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -