oj.uz

Submission #101603

# Submission time Handle Problem Language Result Execution time Memory
101603 2019-03-19T05:02:08 Z dantoh000 Chase (CEOI17_chase) C++14
50 / 100
 4000 ms 94912 KB 
#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 <= 1000){
        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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 85688 KB Output is correct
2 Correct 270 ms 85712 KB Output is correct
3 Correct 297 ms 85696 KB Output is correct
4 Correct 307 ms 85624 KB Output is correct
5 Correct 299 ms 85808 KB Output is correct
6 Correct 289 ms 85752 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 85688 KB Output is correct
2 Correct 270 ms 85712 KB Output is correct
3 Correct 297 ms 85696 KB Output is correct
4 Correct 307 ms 85624 KB Output is correct
5 Correct 299 ms 85808 KB Output is correct
6 Correct 289 ms 85752 KB Output is correct
7 Execution timed out 4014 ms 85732 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2154 ms 94912 KB Output is correct
2 Correct 2293 ms 94852 KB Output is correct
3 Correct 148 ms 91116 KB Output is correct
4 Correct 190 ms 90972 KB Output is correct
5 Correct 961 ms 90984 KB Output is correct
6 Correct 787 ms 90992 KB Output is correct
7 Correct 912 ms 91012 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 85688 KB Output is correct
2 Correct 270 ms 85712 KB Output is correct
3 Correct 297 ms 85696 KB Output is correct
4 Correct 307 ms 85624 KB Output is correct
5 Correct 299 ms 85808 KB Output is correct
6 Correct 289 ms 85752 KB Output is correct
7 Execution timed out 4014 ms 85732 KB Time limit exceeded
8 Halted 0 ms 0 KB -