oj.uz

Submission #67299

# Submission time Handle Problem Language Result Execution time Memory
67299 2018-08-13T20:13:41 Z MANcity Chase (CEOI17_chase) C++14
0 / 100
 17 ms 5744 KB 
///GAGO_O
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int n,k;
LL P[10002];
///sarqi LL
vector<vector<int> > g(100002);
LL dn[100002][102];
LL dv[100002][102];
LL sz[100002];
LL par[100002];
LL ANS[100002];
void dfs(int v,int p)
{
    par[v]=p;
    pair<LL,int> ma1[102];
    pair<LL,int> ma2[102];
    for0(i,k)
    {
        ma1[i].first=0;
        ma2[i].first=0;
        ma1[i].second=-1;
        ma2[i].second=-1;
    }
    for0(i,g[v].size()-1)
    {
        int to=g[v][i];
        if(to!=p)
        {
            dfs(to,v);
            for1(j,k)
            {
                dn[v][j]=max(dn[to][j],dn[to][j-1]+sz[v]-P[p]);
                if(dn[to][j]>ma1[j].first)
                {
                    ma2[j]=ma1[j];
                    ma1[j].first=dn[to][j];
                    ma1[j].second=i;
                }
                else
                if(dn[to][j]>ma2[j].first)
                {
                    ma2[j].first=dn[to][j];
                    ma2[j].second=i;
                }
            }
            for1(j,k)
            {
                LL t=0;
                if(j!=1)
                    t=P[to];
                dv[v][j]=max(dv[v][j],dv[to][j-1]+sz[v]-t);
            }
        }
    }
    ///hishi
    LL ma=0;
    for0(j,k)
    {
        ma=max(dv[v][j],ma);
        ma=max(dn[v][j],ma);
    }
    ANS[v]=max(ANS[v],ma);
    for0(j,k)
    for0(i,g[v].size()-1)
    {
        int to=g[v][i];
        if(to!=p)
        {
            LL S=dv[to][j];
            int q=ma1[k-j].second;
            if(q!=i && q!=-1)
            {
                ANS[v]=max(ANS[v],S+ma1[k-j].first);
            }
            q=ma2[k-j].second;
            if(q!=i && q!=-1)
            {
                ANS[v]=max(ANS[v],S+ma2[k-j].first);
            }
        }
    }
}
int main()
{
    cin>>n>>k;
    for1(i,n)
        cin>>P[i];
    for1(i,n-1)
    {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for1(i,n)
    {
        for0(j,g[i].size()-1)
        {
            int to=g[i][j];
            sz[i]+=P[to];
        }
    }
    dfs(1,-1);
    LL ma=0;
    for1(i,n)
    {
        ma=max(ma,ANS[i]);
    }
    cout<<ma<<endl;
    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 5 ms 2868 KB Output is correct
4 Incorrect 4 ms 2868 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 5 ms 2868 KB Output is correct
4 Incorrect 4 ms 2868 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 5744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 5 ms 2868 KB Output is correct
4 Incorrect 4 ms 2868 KB Output isn't correct
5 Halted 0 ms 0 KB -