Submission #544591

#	Time	Username	Problem	Language	Result	Execution time	Memory
544591		leaked	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	0 / 100	4 ms	4948 KiB

worst_reporter2

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pb push_back
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_resp ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<int,ll> pil;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=2e5+1;
const ll inf=1e18;
vec<int> g[N];
int c[N],a[N],h[N];

ll toadd=0;
map<int,ll> mp;
int cnt[N];
vec<pil> *dps[N];
int dp1[N];
//ll sm[N]
void dfs1(int v){
    dp1[v]=1;
    for(auto &z : g[v]){
        dfs1(z);
        dp1[v]+=dp1[z];
    }
}
void dfs(int v,bool keep=0){
//    cout<<"DFS "<<v<<' '<<h[v]<<endl;
    int big=-1;
    for(auto &z : g[v]){
        if(big==-1 || dp1[z]>dp1[big])
            big=z;
    }
    for(auto &z : g[v]){
        if(z==big) continue;
        dfs(z,0);
    }
    if(big!=-1){
        dfs(big,1);
//        dps[v]=dps[big];
    }
//    else{
    dps[v]=new vec<pil>();
//    }

    for(auto &z : g[v]){
        if(z==big) continue;
        int last=0;
        for(auto &u : *dps[z]){
            mp[u.f]+=u.s;
        }
        (*dps[z]).clear();
    }
    mp[h[v]]-=c[v];
    mp[h[v]+1]+=c[v];
    mp[0]+=c[v];
//    cerr<<"HEY "<<mp[h[v]]<<endl;
    while(mp[h[v]]<=0){
        auto it=mp.lower_bound(h[v]);
        if(it==mp.begin()) break;
        --it;
        mp[h[v]]+=it->s;
        mp.erase(it);
    }
//    for(auto &z : mp)
//        cout<<"DELT "<<v<<' '<<z.f<<' '<<z.s<<endl;
    if(!keep){
        for(auto &u : mp){
            (*dps[v]).pb(u);
        }
        mp.clear();
    }
}
signed main(){
    fast_resp;
    int n;
    cin>>n;
    vec<int>kek;
    for(int i=0;i<n;i++){
        cin>>a[i]>>h[i]>>c[i];--a[i];
        if(a[i]!=i) g[a[i]].pb(i);
        kek.pb(h[i]);
    }
//    sort(all(kek));kek.erase(unique(all(kek)),kek.end());
////    dp1[N]=inf;
//    for(int i=0;i<n;i++) h[i]=lower_bound(all(kek),h[i])-kek.begin();
    dfs1(0);dfs(0);
    ll sm=0;
    for(auto &z : (*dps[0])){
        sm+=z.s;
        if(z.f>0){
            cout<<sm<<endl;
            return 0;
        }
    }
    assert(false);
//    cout<<sm;
    return 0;
}
/*
2
1 89 964898447
2 20 952129455
*/

Compilation message (stderr)

worst_reporter2.cpp: In function 'void dfs(long long int, bool)':
worst_reporter2.cpp:60:13: warning: unused variable 'last' [-Wunused-variable]
   60 |         int last=0;
      |             ^~~~

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