Submission #499921

#	Time	Username	Problem	Language	Result	Execution time	Memory
499921		RambaXGorilla	Chase (CEOI17_chase)	C++17	100 / 100	339 ms	359092 KiB

chase

#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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30