oj.uz

Submission #499921

# Submission time Handle Problem Language Result Execution time Memory
499921 2021-12-30T04:12:59 Z RambaXGorilla Chase (CEOI17_chase) C++17
100 / 100
 339 ms 359092 KB 
#include<cstdio>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair <ll,int> lli;
int N, V;
int pigs[100010];
vector <int> adj[100010];
ll childBest, childUps[110], childDowns[110];
void topTwo(lli a[], lli b){
    if(b > a[0]){
        a[1] = a[0];
        a[0] = b;
    }
    else if(b > a[1]){
        a[1] = b;
    }
}
void recur(int stat, int par){
    lli topUps[110][2] = {}, topDowns[110][2] = {};
    ll best = 0;
    ll surrSum = 0;
    for(int i = 0;i < adj[stat].size();i++){
        surrSum += pigs[adj[stat][i]];
    }
    for(int i = 0;i < adj[stat].size();i++){
        int next = adj[stat][i];
        if(next != par){
            recur(next, stat);
            best = max(best, childBest);
            for(int j = V;j > 0;j--){
                topTwo(topUps[j], lli(max(childUps[j], childUps[j - 1] + surrSum - pigs[next]), next));
                topTwo(topDowns[j], lli(childDowns[j], next));
            }
        }
    }
    topTwo(topUps[1], lli(surrSum, stat));
    for(int i = 0;i < V + 1;i++){
        for(int j = 0;j < 2;j++){
            if(topUps[i][j].second != topDowns[V - i][0].second){
                best = max(best, topUps[i][j].first + topDowns[V - i][0].first);
            }
            else{
                best = max(best, topUps[i][j].first + topDowns[V - i][1].first);
            }
        }
    }
    childBest = best;
    for(int i = V;i > 0;i--){
        childUps[i] = topUps[i][0].first;
        childDowns[i] = max(topDowns[i][0].first, topDowns[i - 1][0].first + surrSum - pigs[par]);
    }
}
int main(){
    scanf("%d%d",&N,&V);
    pigs[0] = 0;
    for(int i = 1;i < N + 1;i++){
        scanf("%d",&pigs[i]);
    }
    for(int i = 0;i < N - 1;i++){
        int a, b;
        scanf("%d%d",&a,&b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    recur(1, 0);
    printf("%lld",childBest);
}

Compilation message

chase.cpp: In function 'void recur(int, int)':
chase.cpp:25:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i = 0;i < adj[stat].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
chase.cpp:28:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i = 0;i < adj[stat].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~
chase.cpp: In function 'int main()':
chase.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d%d",&N,&V);
      |     ~~~~~^~~~~~~~~~~~~~
chase.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d",&pigs[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
chase.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2628 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2604 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2628 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2604 KB Output is correct
7 Correct 5 ms 6092 KB Output is correct
8 Correct 4 ms 6092 KB Output is correct
9 Correct 3 ms 2640 KB Output is correct
10 Correct 4 ms 2764 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 3 ms 2776 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 356088 KB Output is correct
2 Correct 338 ms 354368 KB Output is correct
3 Correct 154 ms 8680 KB Output is correct
4 Correct 86 ms 8468 KB Output is correct
5 Correct 165 ms 8792 KB Output is correct
6 Correct 155 ms 8676 KB Output is correct
7 Correct 171 ms 8644 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2628 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2604 KB Output is correct
7 Correct 5 ms 6092 KB Output is correct
8 Correct 4 ms 6092 KB Output is correct
9 Correct 3 ms 2640 KB Output is correct
10 Correct 4 ms 2764 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 3 ms 2776 KB Output is correct
13 Correct 339 ms 356088 KB Output is correct
14 Correct 338 ms 354368 KB Output is correct
15 Correct 154 ms 8680 KB Output is correct
16 Correct 86 ms 8468 KB Output is correct
17 Correct 165 ms 8792 KB Output is correct
18 Correct 155 ms 8676 KB Output is correct
19 Correct 171 ms 8644 KB Output is correct
20 Correct 160 ms 8396 KB Output is correct
21 Correct 79 ms 8516 KB Output is correct
22 Correct 167 ms 8388 KB Output is correct
23 Correct 77 ms 8508 KB Output is correct
24 Correct 158 ms 8532 KB Output is correct
25 Correct 141 ms 8292 KB Output is correct
26 Correct 324 ms 359072 KB Output is correct
27 Correct 337 ms 359092 KB Output is correct