oj.uz

Submission #544638

# Submission time Handle Problem Language Result Execution time Memory
544638 2022-04-02T14:09:56 Z leaked Worst Reporter 4 (JOI21_worst_reporter4) C++14
0 / 100
 178 ms 200944 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];
int tt=1;
struct segtree{
    ll t[20*N],p[20*N];
    int l[20*N],r[20*N];
    ll d1,d2;
    segtree(){
        t[0]=0;
        fill(t,t+20*N,0);
        fill(l,l+20*N,0);
        fill(r,r+20*N,0);
        fill(p,p+20*N,0);
    }
    void push(int v,int tl,int tr){
        if(!p[v])
            return;
        if(!l[v]) l[v]=tt++;
        if(!r[v]) r[v]=tt++;
        for(auto &u : {l[v],r[v]})
            p[u]+=p[v],t[u]+=p[v];
        p[v]=0;
        return;
    }
    void upd(int i,ll x,int &v,int tl=0,int tr=N-1){
        if(!v)
            v=tt++;
        if(tl==tr){
            t[v]=x;
            return;
        }
        int tm=(tl+tr)>>1;push(v,tl,tr);
        if(tm>=i)
            upd(i,x,l[v],tl,tm);
        else
            upd(i,x,r[v],tm+1,tr);
        t[v]=min(t[l[v]],t[r[v]]);
    }
    ll get(int l1,int r1,int v,int tl=0,int tr=N-1){
        if(!v || tl>r1 || tr<l1)
            return 0;
        if(tl>=l1&&tr<=r1)
            return t[v];
        int tm=(tl+tr)>>1;push(v,tl,tr);
        return min(get(l1,r1,l[v],tl,tm),get(l1,r1,r[v],tm+1,tr));
    }
    int mg(int v,int u,int tl,int tr){
        if(!v && !u)
            return 0;
        if(tl==tr){
            umin(d1,t[v]);umin(d2,t[u]);
            if(!v){
                t[u]=d1+d2;
                return u;
            }
            t[v]=d1+d2;
            return v;
        }

        if(!v){
            umin(d2,t[u]);
            p[u]+=d1;
            t[u]+=d1;
            return u;
        }
        if(!u){
            umin(d1,t[v]);
            p[v]+=d2;
            t[v]+=d2;
            return v;
        }
        push(v,tl,tr);push(u,tl,tr);
        int tm=(tl+tr)>>1;
        r[v]=mg(r[v],r[u],tm+1,tr);
        l[v]=mg(l[v],l[u],tl,tm);
        t[v]=d1+d2;
        return v;
    }
    int Merge(int v,int u){
        d1=d2=0;
        return mg(v,u,0,N-1);
    }
}sega;
ll toadd=0;
//map<int,ll> mp;
int root[N];

void dfs(int v){
//    cout<<"DFS "<<v<<endl;
    for(auto &z : g[v]){
        dfs(z);
        root[v]=sega.Merge(root[v],root[z]);
//        cerr<<"EBAL "<<root[v]<<endl;
    }
//    cout<<"W "<<root[v]<<endl;
//    cout<<sega.get(roo)
//    cout<<"HEY "<<sega.get(root[v],h[v],N-1)<<endl;
    sega.upd(h[v],sega.get(h[v],N-1,root[v])-c[v],root[v]);
}
signed main(){
    fast_resp;
    int n;
    cin>>n;
    vec<int>kek;
    ll sm=0;
    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]);sm+=c[i];
    }
    sort(all(kek));kek.erase(unique(all(kek)),kek.end());
    for(int i=0;i<n;i++) h[i]=lower_bound(all(kek),h[i])-kek.begin();
    dfs(0);
    cout<<sm+sega.get(0,N-1,root[0]);
    return 0;
}
/*
3
1 3 6
1 2 5
1 5 6
6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6
2
1 89 964898447
2 20 952129455
*/

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 98892 KB Output is correct
2 Correct 44 ms 98920 KB Output is correct
3 Correct 41 ms 98892 KB Output is correct
4 Correct 45 ms 98844 KB Output is correct
5 Correct 92 ms 99260 KB Output is correct
6 Correct 47 ms 99148 KB Output is correct
7 Correct 44 ms 99196 KB Output is correct
8 Correct 89 ms 99264 KB Output is correct
9 Correct 48 ms 99232 KB Output is correct
10 Correct 56 ms 99144 KB Output is correct
11 Correct 45 ms 99184 KB Output is correct
12 Correct 44 ms 99720 KB Output is correct
13 Correct 44 ms 99600 KB Output is correct
14 Correct 47 ms 99512 KB Output is correct
15 Correct 45 ms 99460 KB Output is correct
16 Runtime error 178 ms 200944 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 98892 KB Output is correct
2 Correct 44 ms 98920 KB Output is correct
3 Correct 41 ms 98892 KB Output is correct
4 Correct 45 ms 98844 KB Output is correct
5 Correct 92 ms 99260 KB Output is correct
6 Correct 47 ms 99148 KB Output is correct
7 Correct 44 ms 99196 KB Output is correct
8 Correct 89 ms 99264 KB Output is correct
9 Correct 48 ms 99232 KB Output is correct
10 Correct 56 ms 99144 KB Output is correct
11 Correct 45 ms 99184 KB Output is correct
12 Correct 44 ms 99720 KB Output is correct
13 Correct 44 ms 99600 KB Output is correct
14 Correct 47 ms 99512 KB Output is correct
15 Correct 45 ms 99460 KB Output is correct
16 Runtime error 178 ms 200944 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 98892 KB Output is correct
2 Correct 44 ms 98920 KB Output is correct
3 Correct 41 ms 98892 KB Output is correct
4 Correct 45 ms 98844 KB Output is correct
5 Correct 92 ms 99260 KB Output is correct
6 Correct 47 ms 99148 KB Output is correct
7 Correct 44 ms 99196 KB Output is correct
8 Correct 89 ms 99264 KB Output is correct
9 Correct 48 ms 99232 KB Output is correct
10 Correct 56 ms 99144 KB Output is correct
11 Correct 45 ms 99184 KB Output is correct
12 Correct 44 ms 99720 KB Output is correct
13 Correct 44 ms 99600 KB Output is correct
14 Correct 47 ms 99512 KB Output is correct
15 Correct 45 ms 99460 KB Output is correct
16 Runtime error 178 ms 200944 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -