oj.uz

Submission #544589

# Submission time Handle Problem Language Result Execution time Memory
544589 2022-04-02T13:14:22 Z leaked Worst Reporter 4 (JOI21_worst_reporter4) C++14
0 / 100
 3 ms 4948 KB 
#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);

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

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -