oj.uz

Submission #544658

# Submission time Handle Problem Language Result Execution time Memory
544658 2022-04-02T14:16:32 Z leaked Worst Reporter 4 (JOI21_worst_reporter4) C++14
14 / 100
 506 ms 217660 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++;
        assert(tt<20*N);
        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++;
        assert(tt<20*N);
        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;
        }
        int tm=(tl+tr)>>1;
        if(l[u] || r[u]) push(u,tl,tr);
        if(l[v] || r[v]) push(v,tl,tr);
        p[v]=p[u]=0;
        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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 98892 KB Output is correct
2 Correct 40 ms 98892 KB Output is correct
3 Correct 38 ms 98832 KB Output is correct
4 Correct 40 ms 98944 KB Output is correct
5 Correct 46 ms 99148 KB Output is correct
6 Correct 44 ms 99204 KB Output is correct
7 Correct 42 ms 99256 KB Output is correct
8 Correct 51 ms 99248 KB Output is correct
9 Correct 44 ms 99212 KB Output is correct
10 Correct 45 ms 99188 KB Output is correct
11 Correct 45 ms 99148 KB Output is correct
12 Correct 44 ms 99664 KB Output is correct
13 Correct 44 ms 99688 KB Output is correct
14 Correct 45 ms 99404 KB Output is correct
15 Correct 44 ms 99460 KB Output is correct
16 Correct 45 ms 99184 KB Output is correct
17 Correct 46 ms 99228 KB Output is correct
18 Correct 43 ms 99224 KB Output is correct
19 Correct 51 ms 99412 KB Output is correct
20 Correct 51 ms 99436 KB Output is correct
21 Correct 44 ms 99376 KB Output is correct
22 Correct 45 ms 99204 KB Output is correct
23 Correct 43 ms 99148 KB Output is correct
24 Correct 43 ms 99356 KB Output is correct
25 Correct 45 ms 99440 KB Output is correct
26 Correct 47 ms 99816 KB Output is correct
27 Correct 54 ms 99340 KB Output is correct
28 Correct 45 ms 99508 KB Output is correct
29 Correct 43 ms 99592 KB Output is correct
30 Correct 43 ms 99448 KB Output is correct
31 Correct 43 ms 99480 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 98892 KB Output is correct
2 Correct 40 ms 98892 KB Output is correct
3 Correct 38 ms 98832 KB Output is correct
4 Correct 40 ms 98944 KB Output is correct
5 Correct 46 ms 99148 KB Output is correct
6 Correct 44 ms 99204 KB Output is correct
7 Correct 42 ms 99256 KB Output is correct
8 Correct 51 ms 99248 KB Output is correct
9 Correct 44 ms 99212 KB Output is correct
10 Correct 45 ms 99188 KB Output is correct
11 Correct 45 ms 99148 KB Output is correct
12 Correct 44 ms 99664 KB Output is correct
13 Correct 44 ms 99688 KB Output is correct
14 Correct 45 ms 99404 KB Output is correct
15 Correct 44 ms 99460 KB Output is correct
16 Correct 45 ms 99184 KB Output is correct
17 Correct 46 ms 99228 KB Output is correct
18 Correct 43 ms 99224 KB Output is correct
19 Correct 51 ms 99412 KB Output is correct
20 Correct 51 ms 99436 KB Output is correct
21 Correct 44 ms 99376 KB Output is correct
22 Correct 45 ms 99204 KB Output is correct
23 Correct 43 ms 99148 KB Output is correct
24 Correct 43 ms 99356 KB Output is correct
25 Correct 45 ms 99440 KB Output is correct
26 Correct 47 ms 99816 KB Output is correct
27 Correct 54 ms 99340 KB Output is correct
28 Correct 45 ms 99508 KB Output is correct
29 Correct 43 ms 99592 KB Output is correct
30 Correct 43 ms 99448 KB Output is correct
31 Correct 43 ms 99480 KB Output is correct
32 Correct 47 ms 99148 KB Output is correct
33 Runtime error 506 ms 217660 KB Execution killed with signal 6
34 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 98892 KB Output is correct
2 Correct 40 ms 98892 KB Output is correct
3 Correct 38 ms 98832 KB Output is correct
4 Correct 40 ms 98944 KB Output is correct
5 Correct 46 ms 99148 KB Output is correct
6 Correct 44 ms 99204 KB Output is correct
7 Correct 42 ms 99256 KB Output is correct
8 Correct 51 ms 99248 KB Output is correct
9 Correct 44 ms 99212 KB Output is correct
10 Correct 45 ms 99188 KB Output is correct
11 Correct 45 ms 99148 KB Output is correct
12 Correct 44 ms 99664 KB Output is correct
13 Correct 44 ms 99688 KB Output is correct
14 Correct 45 ms 99404 KB Output is correct
15 Correct 44 ms 99460 KB Output is correct
16 Correct 45 ms 99184 KB Output is correct
17 Correct 46 ms 99228 KB Output is correct
18 Correct 43 ms 99224 KB Output is correct
19 Correct 51 ms 99412 KB Output is correct
20 Correct 51 ms 99436 KB Output is correct
21 Correct 44 ms 99376 KB Output is correct
22 Correct 45 ms 99204 KB Output is correct
23 Correct 43 ms 99148 KB Output is correct
24 Correct 43 ms 99356 KB Output is correct
25 Correct 45 ms 99440 KB Output is correct
26 Correct 47 ms 99816 KB Output is correct
27 Correct 54 ms 99340 KB Output is correct
28 Correct 45 ms 99508 KB Output is correct
29 Correct 43 ms 99592 KB Output is correct
30 Correct 43 ms 99448 KB Output is correct
31 Correct 43 ms 99480 KB Output is correct
32 Correct 47 ms 99148 KB Output is correct
33 Runtime error 506 ms 217660 KB Execution killed with signal 6
34 Halted 0 ms 0 KB -