Submission #409289

#	Time	Username	Problem	Language	Result	Execution time	Memory
409289		Hazem	Chase (CEOI17_chase)	C++14	100 / 100	667 ms	488160 KiB

chase

#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>

const int N = 1e5+10;
const int M = 101;
const LL INF = 1e9;
const LL LINF = 2e18;
const LL MOD = 4294967296;
const double PI = 3.141592653589793;

LL dp[N][M];
int a[N];
int mxnode[N][M][2];
pair<LL,LL>mx[N][M][2];

vector<int>adj[N];
int n,k;

void dfs(int i,int pre){

    LL sum = 0;
    for(auto x:adj[i])
        if(x!=pre)
            dfs(x,i),sum += 0ll+a[x];

    for(auto x:adj[i]){
        if(x==pre)continue;
        for(int j=1;j<=100;j++)
            dp[i][j] = max(dp[i][j],max(dp[x][j],dp[x][j-1]+sum));
    }
}

LL ans = 0;
void rootshift(int i,int pre){

    LL sum = 0;
    for(auto x:adj[i])
        sum += 0ll+a[x];

    for(auto x:adj[i])
        for(int j=1;j<=100;j++)
            dp[i][j] = max(dp[i][j],max(dp[x][j],dp[x][j-1]+sum));

    ans = max(ans,dp[i][k]);

    for(auto x:adj[i]){
        for(int j=1;j<=100;j++)
            for(int j1=0;j1<2;j1++){
                LL val = dp[x][j-j1];
                if(val>mx[i][j][j1].F){
                    
                    swap(mx[i][j][j1].F,mx[i][j][j1].S);

                    mx[i][j][j1].F = val;
                    mxnode[i][j][j1] = x;
                }
                else 
                    if(val>mx[i][j][j1].S)
                        mx[i][j][j1].S = val;
            }
    }

    for(auto x:adj[i]){
        if(x==pre)continue;

        sum -= 0ll+a[x];
        for(int j=1;j<=100;j++){
            LL val[2] = {0,0};
            for(int j1=0;j1<2;j1++)
                if(mxnode[i][j][j1]==x)
                    val[j1] = mx[i][j][j1].S;
                else 
                    val[j1] = mx[i][j][j1].F;
            dp[i][j] = max(val[0],val[1]+sum);        
        }
        rootshift(x,i);
        sum += 0ll+a[x];
    }

}

int main(){

    //freopen("out.txt","w",stdout);

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
        
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1,0);
    rootshift(1,0);
    printf("%lld\n",ans);
}   

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
chase.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
chase.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~

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