Submission #386972

#	Time	Username	Problem	Language	Result	Execution time	Memory
386972		egorlifar	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	463 ms	84056 KiB

worst_reporter2

/*
KAMUI!
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓▓▓▓██████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓███▓▓▓▓▓▓▓▓▓▓█████▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓███▓▒▒░▒▒▒▒▒░░░▒▒▒▓▓███▓▓▓▓▓▓▓ 
▓▓▓▓▓▓█▓▒▒▒▓▓████████▓▒▒░▒▒▒▓██▓▓▓▓▓▓
▓▓▓▓██▒▓████████████████▓░▒▒▒▒▓██▓▓▓▓ 
▓▓▓██▓███████▓▒░░░░░░░▒███▒░░▒▒▒██▓▓▓ 
▓▓█████████▓░░░░░░░░░░░░░██▓▓██████▓▓ 
▓▓█▒▓███████████▓▓▒▒▒▓▓██████████▓█▓▓ 
▓██▒▒▒███████████████████████████▓▓█▓ 
▓█▓▒▒░░████████▒░░░░▓███████████▓░▒█▓ 
▓█▒▒▒░██░▒████░░░░░░█████░░████▓░░▒█▓ 
▓█▒▒▒▒██░░░██▓░░░░░░░███▒░░████▒▒▒▒█▓ 
▓█▓▒▒▒██▒░░░▓█▓░░░░░▓█▓░░░▓███▓▒▒░▓█▓ 
▓█▓▒▒▒███░░░░████████▓░░░░░████▒▒▒▓█▓ 
▓▓█▒▒░▓███░░░▒███████▒░░░▒███▓▒▒▒▒█▓▓ 
▓▓██▒▒░████▒░░███████░░░▓███▓░▒▒▒██▓▓ 
▓▓▓██▒▒▒█████▓░░██████▒▓███▓▒░▒▒██▓▓▓ 
▓▓▓▓██▓▒░▓██████████████▓▒░▒▒▒▓██▓▓▓▓ 
▓▓▓▓▓▓██▓░▒▓█████████▒░░▒▒▒▒▓██▓▓▓▓▓▓ 
▓▓▓▓▓▓▓███▓▒▒▓██████▓░▒▒▒▓▓███▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓▓███▓▓▓▓███▓▓▓████▓▓▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓▓▓▓███████████▓▓▓▓▓▓▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
*/
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double; 
const string FILENAME = "input";


#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)

inline int read(){
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x;
}
const int INF=0x3f3f3f3f;
typedef pair<int,int> pi;
/*}
*/
const int MAXN=2e5+233;
int n;
int belong[MAXN],dx[MAXN];
int fa[MAXN],dfn[MAXN],siz[MAXN],cnt,heavy[MAXN],top[MAXN],fat[MAXN],h[MAXN],c[MAXN],a[MAXN];
vector<int> g[MAXN];
vector<int> oldg[MAXN];
vector<int> copi[MAXN];
int root(int u){
    return fa[u]=(fa[u]==u? u:root(fa[u]));
}
void merge(int u,int v){
    fa[root(u)]=root(v);
}
void dfs(int now,int pre){
    heavy[now]=0;
    siz[now]=1;
    dfn[now]=1;
    fat[now]=pre;
    for(auto it:g[now]) if(it!=pre){
        dfs(it,now),siz[now]+=siz[it];  
        if(siz[it]>siz[heavy[now]]||heavy[now]==0) heavy[now]=it;
    }
}
void lab(int now,int pre){
    dfn[now]=++cnt;
    if(heavy[now]){
        top[heavy[now]]=top[now];
        lab(heavy[now],now);
    }
    for(auto it:g[now]) if(it!=pre&&it!=heavy[now]) top[it]=it,lab(it,now);
}
LL dp0=0;
set<pi> fk[MAXN];
int ord[MAXN];
bool cmp(int A,int B){
    return (h[A]!=h[B]? h[A]>h[B]:dfn[A]>dfn[B]);
}
bool cmp2(int A,int B){
    return h[A]<h[B];
}
void Add(int pos,int val){
    int oldpos=pos;
    int oldval=val;
    do{
        int old=pos;
        pos=top[pos];
        //  [dfn[pos],dfn[old] ]
        if(fk[pos].empty()||fk[pos].begin()->FIR>dfn[old]);
        else{
            auto ite=fk[pos].upper_bound(II(dfn[old]+1,0));
            --ite;
            while(val){
                if(ite->SEC>val){
                    pi ore=*ite;
                    fk[pos].erase(ite);
                    ore.SEC-=val;
                    fk[pos].insert(ore);
                    val=0;
                    break;
                }
                else{
                    val-=ite->SEC;
                    if(ite==fk[pos].begin()){
                        fk[pos].erase(ite);
                        break;
                    }
                    auto nex=prev(ite);
                    fk[pos].erase(ite);
                    ite=nex;
                }
            }
        }
        pos=fat[pos];
    }while(pos>=0&&val);
    dp0+=val;
    pos=oldpos;
    fk[top[pos]].insert({dfn[pos],oldval});
}
LL solve(vector<int> cyc);
vector<int> rg[MAXN];
vector<int> ng[MAXN];
stack<int> sta;
bool vis[MAXN];
void dfs1(int now){
    vis[now]=1;
    for(auto it:oldg[now]){
        if(!vis[it]){
            dfs1(it);
        }
    }
    sta.push(now);
}
void dfs2(int now){
    belong[now]=cnt;
    for(auto it:rg[now]){
        if(!belong[it]){
            dfs2(it);
        }
    }
}
void Change(vector<int> cyc){
    for(auto it:cyc)if(!vis[it]) dfs1(it);
    while(!sta.empty()){
        int now=sta.top();
        sta.pop();
        if(!belong[now]){
            ++cnt;
            dfs2(now);
        }
    }
    rb(i,1,cnt) dx[i]=0;
    int root=0;
    for(auto it:cyc) ++dx[belong[it]];
    rb(i,1,cnt) if(dx[i]>=2) root=i;
    vector<int> V;
    for(auto it:cyc) if(belong[it]==root) V.PB(it);
    sort(ALL(V),cmp2);
    for(auto it:cyc) g[it].clear();
    for(auto it:cyc) for(auto itt:oldg[it]){
        if(belong[it]==root&&belong[itt]==root);
        else
        if(belong[it]==root){
            g[V[0]].PB(itt);
        }
        else{
            g[it].PB(itt);
        } 
    }
    g[0].PB(V.back());
    rl(i,V.size()-1,1) g[V[i]].PB(V[i-1]);
    cnt=0;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   // read(FILENAME);
    LL sum=0;
    scanf("%d",&n);
    rb(i,0,n) fa[i]=i;
    rb(i,1,n) a[i]=read(),h[i]=read(),c[i]=read(),sum+=c[i];
    rb(i,1,n) a[i]=(a[i]==i? 0:a[i]);
    rb(i,1,n) merge(a[i],i);
    rb(i,1,n) g[a[i]].PB(i),rg[i].PB(a[i]);
    rb(i,0,n) oldg[i]=g[i];
    dfs(0,-1);
    rb(i,1,n) if(!dfn[i]) copi[root(i)].PB(i);
    rb(i,1,n) if(!copi[i].empty()) Change(copi[i]);
    dfs(0,-1);
    lab(0,-1);
    rb(i,1,n) ord[i]=i;
    sort(ord+1,ord+1+n,cmp);
    rb(I,1,n){
        int i=ord[I];
        Add(i,c[i]);
    }
    sum-=dp0;
    cout<<sum<<endl;
    return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:243:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  243 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~

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