Submission #475539

#	Time	Username	Problem	Language	Result	Execution time	Memory
475539		nafis_shifat	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	0 / 100	19 ms	16008 KiB

worst_reporter2

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int mxn=2e5+5;
const int inf=1e9;


ll c[mxn];
int h[mxn];
vector<int> adj[mxn];

map<int,ll> mp[mxn];

int sz[mxn];
int in[mxn],out[mxn],inv[mxn];
int T = 0;
int n;

void dfs0(int u) {
    sz[u] = 1;
    in[u] = ++T;
    inv[T] = u;
    for(int v : adj[u]) {
        dfs0(v);
        sz[u] += sz[v];
    }
    out[u] = T;
}

struct BIT
{
    ll bit[mxn];
    void init() {
        memset(bit,0,sizeof bit);
    }    

    void update(int p,ll v) {
        if(p <= 0) return;
        for(;p < mxn; p += p&-p) bit[p] += v;
    }
    ll query(int p) {
        ll r = 0;
        for(;p > 0; p -= p&-p) r += bit[p];
        return r;
    }

    void add(int l,int r,ll x) {
        update(l,x);
        update(r + 1, -x);
    }
} bt;




void dfs(int u, bool keep = false) {
    int mx = -1, bigChild = -1;

    // cout<<u<<" "<<keep<<endl;

    for(int v : adj[u]) {
        if(sz[v] > mx) {
            mx = sz[v];
            bigChild = v;
        }
    }
    for(int v : adj[u]) if(v != bigChild) dfs(v);

    if(bigChild != -1) dfs(bigChild,true);

    vector<int> ind;

    for(int v : adj[u]) {
        if(v == bigChild) continue;

        int last = 0;
        ll mv = mp[v][h[v]];
        for(auto x : mp[v]) {
            ll td = x.s;
            if(x.f < h[v]) td = min(td, mv);

            bt.add(last + 1, x.f, td);
            last = x.f;
            ind.push_back(x.f);
        }
    }

    bt.add(1,h[u] - 1, c[u]);
    bt.add(h[u] + 1, n, c[u]);

    ind.push_back(h[u]);
    ind.push_back(1);
    ind.push_back(n);



    ll nc = bt.query(h[u]);

    int lo = 1;
    int hi = h[u] - 1;
    int pos = -1;
    ll rmv = -1;

    while(lo <= hi) {
        int mid = lo + hi >> 1;
        ll v = bt.query(mid);
        if(v > nc) {
            pos = mid;
            rmv = v;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }

    if(pos != -1) {
        bt.add(pos, h[u] - 1, nc - rmv);
    }

    


    // cout<<u<<" "<<h[u]<<" "<<c[u]<<endl;
    // for(int i = 1; i <= n; i++) {
    //     cout<<"DP "<<u<<" "<<i<<" = "<<bt.query(i)<<endl;
    // }

    // cout<<endl<<endl;
    if(!keep) {
        for(int i = in[bigChild]; i <= out[bigChild]; i++) {
            ind.push_back(h[inv[i]]);
        }
        for(int i : ind) {
            mp[u][i] = bt.query(i);
        }
        int last = 0;
        for(auto x : mp[u]) {

            bt.add(last + 1, x.f, -x.s);
            last = x.f;
        }
    }
}





int main() {
    cin >> n;

    vector<int> v;

    for(int i = 1; i <= n; i++) {
        int bap;
        scanf("%d %d %lld",&bap,&h[i],&c[i]);
        if(bap != i) adj[bap].push_back(i);
        v.push_back(h[i]);
    }

    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()), v.end());

    for(int i = 1; i <= n; i++) {
        h[i] = lower_bound(v.begin(),v.end(),h[i]) - v.begin() + 1;
    }
    dfs0(1);

    dfs(1, true);

    cout<<bt.query(1)<<endl;







}

Compilation message (stderr)

worst_reporter2.cpp: In function 'void dfs(int, bool)':
worst_reporter2.cpp:108:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |         int mid = lo + hi >> 1;
      |                   ~~~^~~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:159:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         scanf("%d %d %lld",&bap,&h[i],&c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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