Submission #389774

#	Time	Username	Problem	Language	Result	Execution time	Memory
389774		georgerapeanu	Worst Reporter 4 (JOI21_worst_reporter4)	C++11	79 / 100	926 ms	524292 KiB

worst_reporter2

#include <bits/stdc++.h>

using namespace std;

struct slope_magic_t{
    map<int,long long> slope_change;

    void merge(slope_magic_t &other){
        for(auto it:other.slope_change){
            slope_change[it.first] += it.second;
        }
    }

    void add_value(int value,int cost){
        slope_change[0] += cost;
        slope_change[value] -= cost;
        slope_change[value + 1] += cost;

        long long relative_height = 0;
        map<int,long long> :: iterator it,it2;
        it = slope_change.lower_bound(value);

        long long current_diff = slope_change[value];

        while(current_diff < 0){
            it2 = it;
            if(it2 == slope_change.begin()){
                break;
            }
            it2--;
            if(it2 == slope_change.begin() || current_diff + it2->second > 0){
                it2->second += current_diff;
                slope_change.erase(it);
                break;
            }
            relative_height = -current_diff - it2->second;
            slope_change.erase(it2);
            current_diff = -relative_height;
        }
    }

    int size(){
        return (int)slope_change.size();
    }

    void swap(slope_magic_t &other){
        slope_change.swap(other.slope_change);
    }
};

const int NMAX = 2e5;

int n;
slope_magic_t dp[NMAX + 5];
vector<int> graph[NMAX + 5];
int father[NMAX + 5];
int c[NMAX + 5];
int h[NMAX + 5];

void dfs(int nod,int lvl){
    for(auto it:graph[nod]){
        dfs(it,lvl + 1);
        if(dp[it].size() > dp[nod].size()){
            dp[nod].swap(dp[it]);
        }
        dp[nod].merge(dp[it]);
    }
    dp[nod].add_value(h[nod],c[nod]);
}

int main(){

    scanf("%d",&n);

    for(int i = 1;i <= n;i++){
        scanf("%d %d %d",&father[i],&h[i],&c[i]);
        if(father[i] == i){
            continue;
        }
        graph[father[i]].push_back(i);
    }

    dfs(1,0);
    
    printf("%lld\n",dp[1].slope_change[0]);

    return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
worst_reporter2.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |         scanf("%d %d %d",&father[i],&h[i],&c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 0 / 21