Submission #544693

#	Time	Username	Problem	Language	Result	Execution time	Memory
544693		leaked	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	100 / 100	717 ms	241320 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);
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[40*N],p[40*N];
    int l[40*N],r[40*N];
    ll d1,d2;
    segtree(){
        t[0]=0;
        fill(t,t+40*N,0);
        fill(l,l+40*N,0);
        fill(r,r+40*N,0);
        fill(p,p+40*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<40*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<40*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];
int rt[N],used[N],u[N];
vec<pil> cost[N];
vec<int> ord;
void dfs1(int v){
    if(u[v])
        return;
    u[v]=1;
    for(auto &z : g[v])
        dfs1(z);
    ord.pb(v);
}
void dfs(int v){
    u[v]=0;
//    cout<<"DFS "<<v<<endl;
    for(auto &z : g[v]){
        dfs(z);
        root[v]=sega.Merge(root[v],root[z]);
    }
    for(auto &z : cost[v])
        sega.upd(z.f,sega.get(z.f,N-1,root[v])-z.s,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];
        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();

    for(int i=0;i<n;i++){
        if(used[i]) continue;
        int v=i;
        while(!used[v]){
//            cout<<"CHECK "<<v<<endl;
            used[v]=1;
            v=a[v];
        }
        vec<pil> who;
        map<int,ll> mp;
        ll s=0;
        int st=v;
        while(used[v]==1){
            mp[h[v]]+=c[v];
            s+=c[v];

            rt[v]=st;
            used[v]=2;
//            cerr<<"CYC "<<v<<' ';
            v=a[v];
        }
//        cout<<endl;
        for(auto &z : mp) cost[st].pb(z);
        v=i;
        while(used[v]==1){
            rt[v]=v;
            cost[v].pb({h[v],c[v]});
            used[v]=2;
            v=a[v];
        }
    }
    for(int i=0;i<n;i++){
        if(rt[i]!=rt[a[i]])
            g[rt[a[i]]].pb(rt[i]);
    }
    for(int i=0;i<n;i++){
        if(rt[i]==i)
            dfs1(i);
    }
//    return 0;
    reverse(all(ord));
    for(auto &i : ord){
        if(!u[i]) continue;
//        cout<<"WT "<<i<<endl;
        dfs(i);
        sm+=sega.get(0,N-1,root[i]);
    }
    cout<<sm;
    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 40 952129455
*/

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