Submission #577170

#	Time	Username	Problem	Language	Result	Execution time	Memory
577170		balbit	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	79 / 100	1228 ms	85584 KiB

worst_reporter2

#include <bits/stdc++.h>
#define int ll
#undef BALBIT

using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 2e5+5;

int C[maxn], H[maxn];

// BIT
struct BIT{
    vector<ll> s;
    int MXN;

    ll QU(int e) {ll re = 0; for (++e; e>0; e-=e&-e) re += s[e]; return re;}
    void MO(int e, ll v) {for (++e; e<MXN; e+=e&-e) s[e] += v;}

    BIT(int ss){
        s.resize(ss+1,0); MXN = ss+1;
    }
    BIT(){}
};

vector<int> g[maxn];
int to[maxn];
bool oncyc[maxn];
ll curval[maxn];
int fa[18][maxn];
int inid[maxn], outid[maxn]; // get(i) = inbit(inid[i])  - outbit(outid[i])
int inpos[maxn], outpos[maxn]; // where to update

vector<int> inord;
vector<int> outord;

BIT inbit, outbit;

void dfs(int v, int p) {
    if (p == -1) fa[0][v] = v;
//    bug(v,p);
    inord.pb(v);
    inid[v] = SZ(inord)-1;
    outid[v] = SZ(outord)-1;
    inpos[v] = SZ(inord)-1;
    for (int u : g[v]) {
        if (!oncyc[u] && u != p) {

            fa[0][u] = v;
            dfs(u,v);
        }
    }
    outord.pb(v);
    outpos[v] = SZ(outord)-1;
}

ll get(int v) {
    // get prefix sum!!
    return inbit.QU(inid[v]) - outbit.QU(outid[v]);
}

void upd(int v, ll w) {
    curval[v] += w;
    inbit.MO(inpos[v], w);
    outbit.MO(outpos[v], w);
}


int nxtset(int v) { // lowest (strict) ancestor of v that is set
    if (oncyc[v]) return -1;
    v = fa[0][v];
    int gv = get(v);
    for (int j = 18-1; j>=0; --j) {
        if (gv - get(fa[j][v]) == 0) {
            v = fa[j][v];
        }
    }
    if (curval[v] == 0) {
        assert(oncyc[v]); return -1;
    }
    return v;
}

vector<pair<int, pii> > ha;

void run(int v) {
    inord.clear(); outord.clear();
    dfs(v, -1);

    for( int e : inord) curval[e] = 0;

    for (int j = 1; j<18; ++j) {
        for (int tmp : inord){
            fa[j][tmp] = fa[j-1][fa[j-1][tmp]];
        }
    }

    int sz = SZ(inord);
    inbit = BIT(sz);
    outbit = BIT(sz);

    vector<pii> run;
    for (int x : inord) {
        run.pb({H[x], x});
    }

    sort(ALL(run), [&](pii a, pii b){return a.f != b.f? a.f > b.f : inid[a.s] > inid[b.s];});

    ll re = 0;

    for (pii p : run) {
        int x = p.s;
        int y = nxtset(x);
        ll tochg = C[x];
        upd(x, tochg);
        bug(x,y,"plus", tochg);
        re += tochg;
        while (y != -1) {
            int yo = min(tochg, curval[y]);
            upd(y, -yo); tochg -= yo;
            bug(x,y,-yo);
            re -= yo;
            if (curval[y] > 0 || tochg == 0) break;
            y = nxtset(y);
        }

        bug(re);
        if (SZ(ha) && ha.back().f==H[x] && ha.back().s.f == v) ha.pop_back();
        ha.pb({H[x], {v,re}});

        if (x == v) {
            upd(x, -C[x]); re -= C[x];
            ha.pb({H[x]+1, {v,re}});
        }

    }

//    return {re, re2};
}

bool done[maxn], seen[maxn];

void clr(int v) {
    done[v] = 1;
    for (int u : g[v]) {
        if (!done[u]) {
            clr(u);
        }
    }
}

int tmpnow[maxn];

ll getans(int v) {
    assert(!done[v]);

    bug("working", v);

    clr(v);
    int at = v;
    vector<int> walk;
    while (!seen[at]) {
        walk.pb(at);
        seen[at] = 1;
        at = to[at];
    }

    vector<int> cyc;
    while (walk.back() != at) {
        cyc.pb(walk.back()); walk.pop_back();
    }
    cyc.pb(at);

    #ifdef BALBIT
    bug(SZ(cyc));
    for (int e : cyc) cout<<e<<' ';
    cout<<endl;
    #endif // BALBIT

    // case 1: make everything the minimum

    const ll BIG = 0;

    ll re = 0;

    ha.clear();

    for (int t : cyc) oncyc[t] = 1;

    for (int t : cyc) {
        run(t);
//        ans1 += run(t) - BIG;
    }

    sort(ALL(ha));

    ll ans = 0;

    REP(i, SZ(ha)) {
        auto e = ha[i].s;
        re -= tmpnow[e.f];
        tmpnow[e.f] = e.s;
        re += tmpnow[e.f];
        if (i+1==SZ(ha) || ha[i+1].f != ha[i].f) {
            bug(re);
            MX(ans, re);
        }
    }


//    bug(v, ans1, ans2);


//    for (int t : cyc) {
//        C[t] = 0;
//        ans2 += run(t);
//    }
//
//    bug(ans2);

    return ans;
}

signed main(){
    IOS();

    int n; cin>>n;
    ll totc = 0;
    REP(i,n) {
        cin>>to[i]; --to[i];
        g[i].pb(to[i]); g[to[i]].pb(i);
        cin>>H[i]>>C[i];
        totc += C[i];
    }
    ll re = 0;
    REP(i,n) {
        if (!done[i]) {
            re += getans(i);
        }
    }
    bug(totc, re);
    cout<<totc - re<<endl;



}


/*
4
2 3 2
3 3 1
4 1 2
1 1 2
*/

Compilation message (stderr)

worst_reporter2.cpp: In function 'long long int getans(long long int)':
worst_reporter2.cpp:229:14: warning: unused variable 'BIG' [-Wunused-variable]
  229 |     const ll BIG = 0;
      |              ^~~

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