Submission #101593

#	Time	Username	Problem	Language	Result	Execution time	Memory
101593		jamielim	Chase (CEOI17_chase)	C++14	40 / 100	4037 ms	93464 KiB

chase

#include <bits/stdc++.h>
using namespace std;

int n,v;
vector<int> adj[100005];
long long arr[100005];
long long pigeons[100005];
long long memo[100005][105];
long long dp(int x,int vleft,int p){
    if(memo[x][vleft]!=-1)return memo[x][vleft];
    if(vleft==0)return memo[x][0]=0;
    if(adj[x].size()==0)return memo[x][vleft]=pigeons[x]-(p==-1?0:arr[p]);
    long long ans=0;
    for(int i=0;i<(int)adj[x].size();i++){
        if(adj[x][i]==p)continue;
        ans=max(ans,max(dp(adj[x][i],vleft,x),dp(adj[x][i],vleft-1,x)+pigeons[x]-(p==-1?0:arr[p])));
    }
    return memo[x][vleft]=ans;
}

int main(){
    scanf("%d%d",&n,&v);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    int a,b;
    for(int i=0;i<n-1;i++){
        scanf("%d%d",&a,&b); a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i=0;i<n;i++){
        pigeons[i]=0;
        for(int j=0;j<(int)adj[i].size();j++){
            pigeons[i]+=arr[adj[i][j]];
        }
    }
    if(n<=1000){
        long long ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<=v;k++){
                    memo[j][k]=-1;
                }
            }
            ans=max(ans,dp(i,v,-1));
        }
        printf("%lld",ans);
        return 0;
    }
    memset(memo,-1,sizeof(memo));
    long long ans=dp(0,v,-1);
    for(int i=0;i<50000000/n/v;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<=v;k++){
                memo[j][k]=-1;
            }
        }
        ans=max(ans,dp(rand()%n,v,-1));
    }
    printf("%lld",ans);
}

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:24:27: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d",&arr[i]);
                    ~~~~~~~^
chase.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&v);
     ~~~~~^~~~~~~~~~~~~~
chase.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[i]);
         ~~~~~^~~~~~~~~~~~~~
chase.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b); a--; b--;
         ~~~~~^~~~~~~~~~~~~~

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