Submission #101601

#	Time	Username	Problem	Language	Result	Execution time	Memory
101601		dantoh000	Chase (CEOI17_chase)	C++14	50 / 100	2181 ms	94884 KiB

chase

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 100005;
int p[maxn];
int childsum[maxn];
vector<int> adjlist[maxn];
int memo[maxn][105];
int pa[maxn];
int dp(int id, int x){
    //printf("at %d with %d\n",id,x);
    if (x == 0) return 0;
    if (memo[id][x] != -1) return memo[id][x];
    memo[id][x] = 0;
    //printf("if drop at %d, will encounter %d more pigeons\n",id,childsum[id]);
    for (auto v : adjlist[id]){
        if (pa[id] == v) continue;
        pa[v] = id;
        memo[id][x] = max(memo[id][x],max(dp(v,x),dp(v,x-1)+childsum[id]-p[pa[id]]));
    }
    return memo[id][x];
}
main(){
    memset(memo,-1,sizeof(memo));
    int n,v;
    scanf("%lld%lld",&n,&v);
    for (int i = 1; i <= n; i++) scanf("%lld",&p[i]);
    for (int i = 0; i < n-1; i++){
        int a,b;
        scanf("%lld%lld",&a,&b);
        adjlist[a].push_back(b);
        adjlist[b].push_back(a);
        childsum[a] += p[b];
        childsum[b] += p[a];
    }
    int ans = 0;
    if (n <= 100){
        for (int i = 1; i <= n; i++){
            //printf("\n\nstarting at %d\n",i);
            memset(memo,-1,sizeof(memo));
            memset(pa,-1,sizeof(pa));
            pa[i] = 0;
            //printf("%d\n",dp(i,v));
            ans = max(ans,dp(i,v));
        }
    }
    else{
        ans = dp(1,v);
    }
    printf("%lld",ans);

}

Compilation message (stderr)

chase.cpp:23:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
chase.cpp: In function 'int main()':
chase.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&v);
     ~~~~~^~~~~~~~~~~~~~~~~~
chase.cpp:27:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; i++) scanf("%lld",&p[i]);
                                  ~~~~~^~~~~~~~~~~~~~
chase.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~~~~

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