Submission #386413

#	Time	Username	Problem	Language	Result	Execution time	Memory
386413		haojiandan	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	100 / 100	1227 ms	247020 KiB

worst_reporter2

#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 / 14
• Subtask 2: 65 / 65
• Subtask 3: 21 / 21