oj.uz

Submission #386413

# Submission time Handle Problem Language Result Execution time Memory
386413 2021-04-06T14:04:11 Z haojiandan Worst Reporter 4 (JOI21_worst_reporter4) C++14
100 / 100
 1227 ms 247020 KB 
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
const ll INF=1e18;
const int maxm=(1e7)+10;
const int maxn=(2e5)+10;
int n,fa[maxn];
int lsh[maxn],N,H[maxn],C[maxn];
vector<int> son[maxn];
int tot,ls[maxm],rs[maxm];
ll delta[maxn],ans,mx[maxm],fg[maxm],add[maxm];
int rt[maxn],row,rub[maxm];
void pushup(int root) {
	mx[root]=max(mx[ls[root]],mx[rs[root]]);
}
void F(int &root) {
	if (!root) {
		if (row) root=rub[row],row--;
		else root=++tot;
		ls[root]=rs[root]=0;
		mx[root]=add[root]=0,fg[root]=INF;
	}
}
void putadd(int root,ll delta) {
	if (fg[root]!=INF) fg[root]+=delta;
	else add[root]+=delta;
	mx[root]+=delta;
}
void putfg(int root,ll delta) {
	fg[root]=mx[root]=delta; add[root]=0;
}
void pushdown(int root) {
	if (fg[root]==INF&&add[root]==0) return;
	F(ls[root]),F(rs[root]);
	if (fg[root]!=INF) {
		putfg(ls[root],fg[root]);
		putfg(rs[root],fg[root]);
		fg[root]=INF;
	}
	if (add[root]!=0) {
		putadd(ls[root],add[root]);
		putadd(rs[root],add[root]);
		add[root]=0;
	}
}		
int merge(int l,int r,int x,int y) {
	if (!x||!y) return x+y;
	if (l==r) { mx[x]+=mx[y]; return x; }
	if (fg[x]!=INF) swap(x,y);
	if (fg[y]!=INF) {
		assert(add[y]==0);
		putadd(x,add[y]+fg[y]);
		return x;
	}
	add[x]+=add[y];
	int mid=(l+r)>>1;
	ls[x]=merge(l,mid,ls[x],ls[y]);
	rs[x]=merge(mid+1,r,rs[x],rs[y]);
	rub[++row]=y;
	pushup(x);
	if (fg[x]!=INF) mx[x]=fg[x];
	mx[x]+=add[x];
	return x;
}
ll query(int x,int l,int r,int &root) {
	if (l==r) return mx[root];
	int mid=(l+r)>>1; pushdown(root);
	if (x<=mid) return query(x,l,mid,ls[root]);
	return query(x,mid+1,r,rs[root]);
}
void change(int L,int R,int l,int r,int &root,ll delta) {
	F(root);
	if (L<=l&&r<=R) {
		putfg(root,delta);
		return;
	}
	int mid=(l+r)>>1; pushdown(root);
	if (L<=mid) change(L,R,l,mid,ls[root],delta);
	if (mid<R) change(L,R,mid+1,r,rs[root],delta);
	pushup(root);
}
int find(int x,int l,int r,int root,ll delta) {
	if (l==r) return l;
	int mid=(l+r)>>1; pushdown(root);
	if (x<=mid) return find(x,l,mid,ls[root],delta);
	if (mx[ls[root]]>delta) return find(mid,l,mid,ls[root],delta);
	return find(x,mid+1,r,rs[root],delta);
}
int in[maxn],cyc[maxn],vis[maxn];
int cnt,d[maxn],st[maxn],top;
void dfs(int u) {
	st[++top]=u;
	
	delta[u]=C[u];
	change(H[u],H[u],1,N,rt[u],-C[u]);
	//for (int i=1;i<=N;i++) if (i!=H[u]) dp[u][i]+=C[u];
//	printf("? %d\n",u);
//	for (int i=1;i<=N;i++) printf("%lld ",query(i,1,N,rt[u])+delta[u]); puts("");
	
	for (int v : son[u]) if (!cyc[v]) {
		dfs(v);
		delta[u]+=delta[v];
		//printf("mergein %d %d\n",u,v);
		rt[u]=merge(1,N,rt[u],rt[v]);
		//printf("mergeout %d %d\n",u,v);
		/*for (int i=1;i<=N;i++) {
			dp[u][i]+=dp[v][i];
		}*/
	}
	if (!cyc[u]) {
		ll x=query(H[u],1,N,rt[u]);
		//printf("%lld\n",x+delta[u]);
		int pos=find(H[u],1,N,rt[u],x);
		assert(pos<=H[u]);
	//	printf("pos=%d %d\n",pos,H[u]);
		change(pos,H[u],1,N,rt[u],x);
	}
//	for (int i=1;i<=H[u];i++) dp[u][i]=min(dp[u][i],dp[u][H[u]]);
//	printf("u=%d : ",u);
//	for (int i=1;i<=N;i++) printf("%lld ",query(i,1,N,rt[u])+delta[u]); puts("");
}


queue<int> q;
int main() {
	//freopen("1.txt","r",stdin);
	read(n);
	for (int i=1;i<=n;i++) {
		read(fa[i]),read(H[i]),read(C[i]);
		son[fa[i]].push_back(i);
		in[fa[i]]++;
		lsh[++N]=H[i];
		cyc[i]=1;
	}
	sort(lsh+1,lsh+N+1); N=unique(lsh+1,lsh+N+1)-lsh-1;
	for (int i=1;i<=n;i++) H[i]=lower_bound(lsh+1,lsh+N+1,H[i])-lsh;
	
	//for (int i=1;i<=n;i++) printf("%d ",H[i]); puts("");
	for (int i=1;i<=n;i++) if (!in[i]) q.push(i);
	while (!q.empty()) {
		int u=q.front(); q.pop(); cyc[u]=0;
		int v=fa[u];
		in[v]--; if (!in[v]) q.push(v);
	}
	//for (int i=1;i<=n;i++) if (cyc[i]) printf("%d\n",i);
	ans=0;
	for (int i=1;i<=n;i++) if (cyc[i]&&!vis[i]) {
		int x=i; cnt=0; top=0;
		while (1) {
			x=fa[x]; d[++cnt]=x; vis[x]=1;
			if (x==i) break;
		}
		int R=0;
		for (int j=1;j<=cnt;j++) {
			dfs(d[j]);
		//	printf("HI %d\n",d[j]);
			putadd(rt[d[j]],delta[d[j]]);
			R=merge(1,N,R,rt[d[j]]);
		}
	//	printf("? %d\n",R);
	//	for (int j=1;j<=top;j++) printf("%d ",st[j]); puts("");
		ll tmp=INF;
		for (int j=1;j<=top;j++) tmp=min(tmp,query(H[st[j]],1,N,R));
	//	printf("%lld\n",tmp);
		ans+=tmp;
		
	}
	printf("%lld\n",ans);
//	printf("%d\n",tot);
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 6 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 16 ms 7788 KB Output is correct
6 Correct 10 ms 6508 KB Output is correct
7 Correct 13 ms 5868 KB Output is correct
8 Correct 24 ms 7916 KB Output is correct
9 Correct 16 ms 6508 KB Output is correct
10 Correct 10 ms 5868 KB Output is correct
11 Correct 6 ms 5612 KB Output is correct
12 Correct 14 ms 8044 KB Output is correct
13 Correct 7 ms 6636 KB Output is correct
14 Correct 14 ms 7788 KB Output is correct
15 Correct 9 ms 6508 KB Output is correct
16 Correct 17 ms 7916 KB Output is correct
17 Correct 10 ms 6508 KB Output is correct
18 Correct 5 ms 5612 KB Output is correct
19 Correct 23 ms 6764 KB Output is correct
20 Correct 15 ms 6252 KB Output is correct
21 Correct 10 ms 5868 KB Output is correct
22 Correct 12 ms 6636 KB Output is correct
23 Correct 8 ms 5996 KB Output is correct
24 Correct 13 ms 7404 KB Output is correct
25 Correct 9 ms 6636 KB Output is correct
26 Correct 19 ms 8172 KB Output is correct
27 Correct 13 ms 7148 KB Output is correct
28 Correct 14 ms 7276 KB Output is correct
29 Correct 15 ms 7404 KB Output is correct
30 Correct 13 ms 7020 KB Output is correct
31 Correct 13 ms 7020 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 7936 KB Output is correct
2 Correct 1227 ms 156676 KB Output is correct
3 Correct 472 ms 85740 KB Output is correct
4 Correct 1155 ms 156652 KB Output is correct
5 Correct 468 ms 85484 KB Output is correct
6 Correct 223 ms 31596 KB Output is correct
7 Correct 138 ms 22764 KB Output is correct
8 Correct 775 ms 154544 KB Output is correct
9 Correct 322 ms 109804 KB Output is correct
10 Correct 149 ms 57964 KB Output is correct
11 Correct 865 ms 148364 KB Output is correct
12 Correct 333 ms 75564 KB Output is correct
13 Correct 1039 ms 157404 KB Output is correct
14 Correct 376 ms 83436 KB Output is correct
15 Correct 68 ms 22380 KB Output is correct
16 Correct 842 ms 86172 KB Output is correct
17 Correct 327 ms 59884 KB Output is correct
18 Correct 106 ms 34668 KB Output is correct
19 Correct 770 ms 84464 KB Output is correct
20 Correct 283 ms 50912 KB Output is correct
21 Correct 815 ms 123756 KB Output is correct
22 Correct 300 ms 81240 KB Output is correct
23 Correct 464 ms 164972 KB Output is correct
24 Correct 637 ms 111980 KB Output is correct
25 Correct 591 ms 119404 KB Output is correct
26 Correct 569 ms 136556 KB Output is correct
27 Correct 554 ms 100332 KB Output is correct
28 Correct 560 ms 100204 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 6 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 16 ms 7788 KB Output is correct
6 Correct 10 ms 6508 KB Output is correct
7 Correct 13 ms 5868 KB Output is correct
8 Correct 24 ms 7916 KB Output is correct
9 Correct 16 ms 6508 KB Output is correct
10 Correct 10 ms 5868 KB Output is correct
11 Correct 6 ms 5612 KB Output is correct
12 Correct 14 ms 8044 KB Output is correct
13 Correct 7 ms 6636 KB Output is correct
14 Correct 14 ms 7788 KB Output is correct
15 Correct 9 ms 6508 KB Output is correct
16 Correct 17 ms 7916 KB Output is correct
17 Correct 10 ms 6508 KB Output is correct
18 Correct 5 ms 5612 KB Output is correct
19 Correct 23 ms 6764 KB Output is correct
20 Correct 15 ms 6252 KB Output is correct
21 Correct 10 ms 5868 KB Output is correct
22 Correct 12 ms 6636 KB Output is correct
23 Correct 8 ms 5996 KB Output is correct
24 Correct 13 ms 7404 KB Output is correct
25 Correct 9 ms 6636 KB Output is correct
26 Correct 19 ms 8172 KB Output is correct
27 Correct 13 ms 7148 KB Output is correct
28 Correct 14 ms 7276 KB Output is correct
29 Correct 15 ms 7404 KB Output is correct
30 Correct 13 ms 7020 KB Output is correct
31 Correct 13 ms 7020 KB Output is correct
32 Correct 17 ms 7936 KB Output is correct
33 Correct 1227 ms 156676 KB Output is correct
34 Correct 472 ms 85740 KB Output is correct
35 Correct 1155 ms 156652 KB Output is correct
36 Correct 468 ms 85484 KB Output is correct
37 Correct 223 ms 31596 KB Output is correct
38 Correct 138 ms 22764 KB Output is correct
39 Correct 775 ms 154544 KB Output is correct
40 Correct 322 ms 109804 KB Output is correct
41 Correct 149 ms 57964 KB Output is correct
42 Correct 865 ms 148364 KB Output is correct
43 Correct 333 ms 75564 KB Output is correct
44 Correct 1039 ms 157404 KB Output is correct
45 Correct 376 ms 83436 KB Output is correct
46 Correct 68 ms 22380 KB Output is correct
47 Correct 842 ms 86172 KB Output is correct
48 Correct 327 ms 59884 KB Output is correct
49 Correct 106 ms 34668 KB Output is correct
50 Correct 770 ms 84464 KB Output is correct
51 Correct 283 ms 50912 KB Output is correct
52 Correct 815 ms 123756 KB Output is correct
53 Correct 300 ms 81240 KB Output is correct
54 Correct 464 ms 164972 KB Output is correct
55 Correct 637 ms 111980 KB Output is correct
56 Correct 591 ms 119404 KB Output is correct
57 Correct 569 ms 136556 KB Output is correct
58 Correct 554 ms 100332 KB Output is correct
59 Correct 560 ms 100204 KB Output is correct
60 Correct 4 ms 5100 KB Output is correct
61 Correct 5 ms 5100 KB Output is correct
62 Correct 5 ms 5100 KB Output is correct
63 Correct 5 ms 5100 KB Output is correct
64 Correct 1181 ms 164560 KB Output is correct
65 Correct 566 ms 86128 KB Output is correct
66 Correct 1171 ms 169532 KB Output is correct
67 Correct 472 ms 85740 KB Output is correct
68 Correct 205 ms 31468 KB Output is correct
69 Correct 154 ms 23660 KB Output is correct
70 Correct 594 ms 45804 KB Output is correct
71 Correct 309 ms 26348 KB Output is correct
72 Correct 586 ms 33324 KB Output is correct
73 Correct 300 ms 27120 KB Output is correct
74 Correct 825 ms 59304 KB Output is correct
75 Correct 360 ms 39404 KB Output is correct
76 Correct 187 ms 27144 KB Output is correct
77 Correct 722 ms 60092 KB Output is correct
78 Correct 294 ms 39784 KB Output is correct
79 Correct 849 ms 96264 KB Output is correct
80 Correct 396 ms 56812 KB Output is correct
81 Correct 206 ms 29548 KB Output is correct
82 Correct 418 ms 33388 KB Output is correct
83 Correct 417 ms 247020 KB Output is correct
84 Correct 741 ms 83816 KB Output is correct
85 Correct 743 ms 79616 KB Output is correct
86 Correct 742 ms 73452 KB Output is correct
87 Correct 760 ms 83820 KB Output is correct
88 Correct 740 ms 82316 KB Output is correct