Submission #386972

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
386972	2021-04-07T17:44:51 Z	egorlifar	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	463 ms	84056 KB

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

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.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	33260 KB	Output is correct
2	Correct	21 ms	33260 KB	Output is correct
3	Correct	22 ms	33364 KB	Output is correct
4	Correct	22 ms	33260 KB	Output is correct
5	Correct	25 ms	34156 KB	Output is correct
6	Correct	26 ms	34156 KB	Output is correct
7	Correct	26 ms	34156 KB	Output is correct
8	Correct	26 ms	34156 KB	Output is correct
9	Correct	29 ms	34156 KB	Output is correct
10	Correct	26 ms	34156 KB	Output is correct
11	Correct	25 ms	34156 KB	Output is correct
12	Correct	25 ms	34540 KB	Output is correct
13	Correct	25 ms	34540 KB	Output is correct
14	Correct	26 ms	34284 KB	Output is correct
15	Correct	26 ms	34284 KB	Output is correct
16	Correct	25 ms	34156 KB	Output is correct
17	Correct	24 ms	34156 KB	Output is correct
18	Correct	24 ms	34176 KB	Output is correct
19	Correct	26 ms	34284 KB	Output is correct
20	Correct	25 ms	34284 KB	Output is correct
21	Correct	25 ms	34284 KB	Output is correct
22	Correct	24 ms	34028 KB	Output is correct
23	Correct	27 ms	34028 KB	Output is correct
24	Correct	24 ms	34284 KB	Output is correct
25	Correct	24 ms	34284 KB	Output is correct
26	Correct	24 ms	34540 KB	Output is correct
27	Correct	25 ms	34156 KB	Output is correct
28	Correct	28 ms	34284 KB	Output is correct
29	Correct	25 ms	34412 KB	Output is correct
30	Correct	24 ms	34284 KB	Output is correct
31	Correct	25 ms	34284 KB	Output is correct

Subtask #2

65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	34156 KB	Output is correct
2	Correct	349 ms	65772 KB	Output is correct
3	Correct	369 ms	65900 KB	Output is correct
4	Correct	352 ms	65900 KB	Output is correct
5	Correct	337 ms	65772 KB	Output is correct
6	Correct	324 ms	66352 KB	Output is correct
7	Correct	326 ms	68076 KB	Output is correct
8	Correct	240 ms	80748 KB	Output is correct
9	Correct	225 ms	80876 KB	Output is correct
10	Correct	205 ms	82668 KB	Output is correct
11	Correct	223 ms	72940 KB	Output is correct
12	Correct	227 ms	73068 KB	Output is correct
13	Correct	255 ms	65132 KB	Output is correct
14	Correct	244 ms	65132 KB	Output is correct
15	Correct	145 ms	68112 KB	Output is correct
16	Correct	187 ms	71228 KB	Output is correct
17	Correct	186 ms	71276 KB	Output is correct
18	Correct	168 ms	72300 KB	Output is correct
19	Correct	169 ms	62560 KB	Output is correct
20	Correct	156 ms	62688 KB	Output is correct
21	Correct	172 ms	72120 KB	Output is correct
22	Correct	184 ms	72036 KB	Output is correct
23	Correct	129 ms	80876 KB	Output is correct
24	Correct	272 ms	71500 KB	Output is correct
25	Correct	245 ms	77420 KB	Output is correct
26	Correct	221 ms	82540 KB	Output is correct
27	Correct	158 ms	72172 KB	Output is correct
28	Correct	161 ms	72172 KB	Output is correct

Subtask #3

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	33260 KB	Output is correct
2	Correct	21 ms	33260 KB	Output is correct
3	Correct	22 ms	33364 KB	Output is correct
4	Correct	22 ms	33260 KB	Output is correct
5	Correct	25 ms	34156 KB	Output is correct
6	Correct	26 ms	34156 KB	Output is correct
7	Correct	26 ms	34156 KB	Output is correct
8	Correct	26 ms	34156 KB	Output is correct
9	Correct	29 ms	34156 KB	Output is correct
10	Correct	26 ms	34156 KB	Output is correct
11	Correct	25 ms	34156 KB	Output is correct
12	Correct	25 ms	34540 KB	Output is correct
13	Correct	25 ms	34540 KB	Output is correct
14	Correct	26 ms	34284 KB	Output is correct
15	Correct	26 ms	34284 KB	Output is correct
16	Correct	25 ms	34156 KB	Output is correct
17	Correct	24 ms	34156 KB	Output is correct
18	Correct	24 ms	34176 KB	Output is correct
19	Correct	26 ms	34284 KB	Output is correct
20	Correct	25 ms	34284 KB	Output is correct
21	Correct	25 ms	34284 KB	Output is correct
22	Correct	24 ms	34028 KB	Output is correct
23	Correct	27 ms	34028 KB	Output is correct
24	Correct	24 ms	34284 KB	Output is correct
25	Correct	24 ms	34284 KB	Output is correct
26	Correct	24 ms	34540 KB	Output is correct
27	Correct	25 ms	34156 KB	Output is correct
28	Correct	28 ms	34284 KB	Output is correct
29	Correct	25 ms	34412 KB	Output is correct
30	Correct	24 ms	34284 KB	Output is correct
31	Correct	25 ms	34284 KB	Output is correct
32	Correct	25 ms	34156 KB	Output is correct
33	Correct	349 ms	65772 KB	Output is correct
34	Correct	369 ms	65900 KB	Output is correct
35	Correct	352 ms	65900 KB	Output is correct
36	Correct	337 ms	65772 KB	Output is correct
37	Correct	324 ms	66352 KB	Output is correct
38	Correct	326 ms	68076 KB	Output is correct
39	Correct	240 ms	80748 KB	Output is correct
40	Correct	225 ms	80876 KB	Output is correct
41	Correct	205 ms	82668 KB	Output is correct
42	Correct	223 ms	72940 KB	Output is correct
43	Correct	227 ms	73068 KB	Output is correct
44	Correct	255 ms	65132 KB	Output is correct
45	Correct	244 ms	65132 KB	Output is correct
46	Correct	145 ms	68112 KB	Output is correct
47	Correct	187 ms	71228 KB	Output is correct
48	Correct	186 ms	71276 KB	Output is correct
49	Correct	168 ms	72300 KB	Output is correct
50	Correct	169 ms	62560 KB	Output is correct
51	Correct	156 ms	62688 KB	Output is correct
52	Correct	172 ms	72120 KB	Output is correct
53	Correct	184 ms	72036 KB	Output is correct
54	Correct	129 ms	80876 KB	Output is correct
55	Correct	272 ms	71500 KB	Output is correct
56	Correct	245 ms	77420 KB	Output is correct
57	Correct	221 ms	82540 KB	Output is correct
58	Correct	158 ms	72172 KB	Output is correct
59	Correct	161 ms	72172 KB	Output is correct
60	Correct	22 ms	33260 KB	Output is correct
61	Correct	22 ms	33260 KB	Output is correct
62	Correct	22 ms	33260 KB	Output is correct
63	Correct	22 ms	33260 KB	Output is correct
64	Correct	389 ms	68952 KB	Output is correct
65	Correct	432 ms	68644 KB	Output is correct
66	Correct	433 ms	68944 KB	Output is correct
67	Correct	408 ms	68816 KB	Output is correct
68	Correct	368 ms	69532 KB	Output is correct
69	Correct	359 ms	72080 KB	Output is correct
70	Correct	447 ms	79020 KB	Output is correct
71	Correct	438 ms	75368 KB	Output is correct
72	Correct	431 ms	83904 KB	Output is correct
73	Correct	463 ms	84056 KB	Output is correct
74	Correct	365 ms	73808 KB	Output is correct
75	Correct	386 ms	73936 KB	Output is correct
76	Correct	359 ms	74832 KB	Output is correct
77	Correct	313 ms	74660 KB	Output is correct
78	Correct	347 ms	74704 KB	Output is correct
79	Correct	410 ms	75604 KB	Output is correct
80	Correct	445 ms	75480 KB	Output is correct
81	Correct	389 ms	76740 KB	Output is correct
82	Correct	405 ms	84032 KB	Output is correct
83	Correct	170 ms	63456 KB	Output is correct
84	Correct	397 ms	77676 KB	Output is correct
85	Correct	431 ms	77776 KB	Output is correct
86	Correct	386 ms	77520 KB	Output is correct
87	Correct	408 ms	77648 KB	Output is correct
88	Correct	386 ms	77656 KB	Output is correct