oj.uz

Submission #101610

# Submission time Handle Problem Language Result Execution time Memory
101610 2019-03-19T05:11:45 Z dantoh000 Chase (CEOI17_chase) C++14
70 / 100
 2413 ms 94880 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(){
    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);
            for (int k = 1; k <= 1000; k++){
                pa[k] = -1;
                for (int l = 0; l <= v; l++){
                    memo[k][l] = -1;
                }
            }
            pa[i] = 0;
            //printf("%d\n",dp(i,v));
            ans = max(ans,dp(i,v));
        }
    }
    else{
        memset(memo,-1,sizeof(memo));
        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:25: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: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("%lld",&p[i]);
                                  ~~~~~^~~~~~~~~~~~~~
chase.cpp:29: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 5 ms 3456 KB Output is correct
2 Correct 5 ms 3456 KB Output is correct
3 Correct 5 ms 3456 KB Output is correct
4 Correct 5 ms 3556 KB Output is correct
5 Correct 5 ms 3456 KB Output is correct
6 Correct 6 ms 3584 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 5 ms 3456 KB Output is correct
3 Correct 5 ms 3456 KB Output is correct
4 Correct 5 ms 3556 KB Output is correct
5 Correct 5 ms 3456 KB Output is correct
6 Correct 6 ms 3584 KB Output is correct
7 Correct 1464 ms 3648 KB Output is correct
8 Correct 114 ms 3556 KB Output is correct
9 Correct 50 ms 3584 KB Output is correct
10 Correct 272 ms 3604 KB Output is correct
11 Correct 253 ms 3584 KB Output is correct
12 Correct 255 ms 3704 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2413 ms 94880 KB Output is correct
2 Correct 2105 ms 94860 KB Output is correct
3 Correct 170 ms 91180 KB Output is correct
4 Correct 194 ms 90964 KB Output is correct
5 Correct 858 ms 90992 KB Output is correct
6 Correct 742 ms 90996 KB Output is correct
7 Correct 859 ms 91060 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3456 KB Output is correct
2 Correct 5 ms 3456 KB Output is correct
3 Correct 5 ms 3456 KB Output is correct
4 Correct 5 ms 3556 KB Output is correct
5 Correct 5 ms 3456 KB Output is correct
6 Correct 6 ms 3584 KB Output is correct
7 Correct 1464 ms 3648 KB Output is correct
8 Correct 114 ms 3556 KB Output is correct
9 Correct 50 ms 3584 KB Output is correct
10 Correct 272 ms 3604 KB Output is correct
11 Correct 253 ms 3584 KB Output is correct
12 Correct 255 ms 3704 KB Output is correct
13 Correct 2413 ms 94880 KB Output is correct
14 Correct 2105 ms 94860 KB Output is correct
15 Correct 170 ms 91180 KB Output is correct
16 Correct 194 ms 90964 KB Output is correct
17 Correct 858 ms 90992 KB Output is correct
18 Correct 742 ms 90996 KB Output is correct
19 Correct 859 ms 91060 KB Output is correct
20 Incorrect 291 ms 90968 KB Output isn't correct
21 Halted 0 ms 0 KB -