Submission #386402

#	Time	Username	Problem	Language	Result	Execution time	Memory
386402		haojiandan	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	0 / 100	506 ms	8172 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,tr[maxm],mx[maxm],lazy[maxm];
int rt[maxn],row,rub[maxm];
void pushup(int root) {
	tr[root]=tr[ls[root]]+tr[rs[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]=0,lazy[root]=INF;
		tr[root]=0;
	}
}
void pushdown(int root,int l,int r,int mid) {
	if (lazy[root]==INF) return;
	F(ls[root]),F(rs[root]);
	lazy[ls[root]]=lazy[rs[root]]=mx[ls[root]]=mx[rs[root]]=lazy[root];
	tr[ls[root]]=lazy[root]*(mid-l+1);
	tr[rs[root]]=lazy[root]*(r-mid);
	lazy[root]=INF;
}
int merge(int l,int r,int x,int y) {
	if (!x||!y) return x+y;
	if (l==r) {
		tr[x]+=tr[y]; mx[x]=tr[x];
		rub[++row]=y;
		return x;
	}
	int mid=(l+r)>>1;
	pushdown(x,l,r,mid),pushdown(y,l,r,mid);
	ls[x]=merge(l,mid,ls[x],ls[y]);
	rs[x]=merge(mid+1,r,rs[x],rs[y]);
	rub[++row]=y;
	pushup(x);
	return x;
}
ll query(int x,int l,int r,int &root) {
	if (l==r) return tr[root];
	int mid=(l+r)>>1; pushdown(root,l,r,mid);
	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>r) assert(0);
	if (L<=l&&r<=R) {
		tr[root]=delta*(r-l+1);
		lazy[root]=mx[root]=delta;
		return;
	}
	int mid=(l+r)>>1; pushdown(root,l,r,mid);
	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) {
	//printf("%d %d\n",l,r);
	//if (l>r) exit(0);
	if (l==r) return l;
	int mid=(l+r)>>1; pushdown(root,l,r,mid);
	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);
}
void dfs(int u) {
	delta[u]=C[u];
	change(H[u],H[u],1,N,rt[u],-C[u]);
	//printf("u1=%d : ",u);
	//for (int i=1;i<=N;i++) printf("%lld ",query(i,1,N,rt[u])+delta[u]); puts("");
	//for (int i=1;i<=N;i++) if (i!=H[u]) dp[u][i]+=C[u];
	printf("? %d\n",u);
	for (int v : son[u]) {
		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];
		}*/
	}
	ll x=query(H[u],1,N,rt[u]);
	int pos=find(H[u],1,N,rt[u],x);
	//printf("pos=%d\n",pos);
	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("");
}

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]);
		if (i!=1) son[fa[i]].push_back(i);
		lsh[++N]=H[i];
	}
	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("");
	
	dfs(1);
	ans=INF;
	for (int i=1;i<=N;i++) ans=min(ans,query(i,1,N,rt[1])+delta[1]);
	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: 0 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21