oj.uz

Submission #101599

# Submission time Handle Problem Language Result Execution time Memory
101599 2019-03-19T05:00:32 Z dantoh000 Chase (CEOI17_chase) C++14
0 / 100
 2400 ms 52048 KB 
#include <bits/stdc++.h>
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];
}
int main(){
    memset(memo,-1,sizeof(memo));
    int n,v;
    scanf("%d%d",&n,&v);
    for (int i = 1; i <= n; i++) scanf("%d",&p[i]);
    for (int i = 0; i < n-1; i++){
        int a,b;
        scanf("%d%d",&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("%d",ans);

}

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:25: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:26: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("%d",&p[i]);
                                  ~~~~~^~~~~~~~~~~~
chase.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 44152 KB Output is correct
2 Correct 163 ms 44152 KB Output is correct
3 Incorrect 158 ms 44200 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 44152 KB Output is correct
2 Correct 163 ms 44152 KB Output is correct
3 Incorrect 158 ms 44200 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2400 ms 52048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 44152 KB Output is correct
2 Correct 163 ms 44152 KB Output is correct
3 Incorrect 158 ms 44200 KB Output isn't correct
4 Halted 0 ms 0 KB -