Submission #442062

#	Time	Username	Problem	Language	Result	Execution time	Memory
442062		kig9981	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	451 ms	107060 KiB

worst_reporter2

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

vector<int> adj[200000];
map<int,long long> D[200000];
long long O[200000];
int P[200000], H[200000], C[200000], R[200000], cnt[200000];

void dfs(int c)
{
	long long v=C[c], m;
	for(auto n: adj[c]) {
		dfs(n);
		if(D[R[c]].size()<D[R[n]].size()) swap(R[c],R[n]);
		for(auto[a,b]: D[R[n]]) D[R[c]][a]+=b;
		O[c]+=O[n];
	}
	O[c]+=C[c];
	D[R[c]][H[c]]+=C[c];
	if(cnt[c]) {
		D[R[c]][H[c]+1]-=C[c];
		return;
	}
	while(v) {
		auto it=D[R[c]].upper_bound(H[c]);
		if(it==D[R[c]].end()) break;
		m=min(v,it->second);
		it->second-=m;
		v-=m;
		if(it->second==0) D[R[c]].erase(it);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N;
	long long ans=0;
	queue<int> Q;
	cin>>N;
	for(int i=0;i<N;i++) {
		cin>>P[i]>>H[i]>>C[i];
		H[R[i]=i]=1000000000-H[i];
		cnt[--P[i]]++;
	}
	for(int i=0;i<N;i++) if(cnt[i]==0) Q.push(i);
	while(!Q.empty()) {
		int c=Q.front();
		Q.pop();
		if(--cnt[P[c]]==0) Q.push(P[c]);
	}
	for(int i=0;i<N;i++) if(cnt[i]==0) adj[P[i]].push_back(i);
	for(int i=0;i<N;i++) if(cnt[i]) dfs(i);
	for(int i=0;i<N;i++) if(cnt[i]) {
		long long mn;
		cnt[i]--;
		for(int p=P[i];p!=i;p=P[p]) {
			cnt[p]--;
			if(D[R[p]].size()>D[R[i]].size()) swap(R[p],R[i]);
			for(auto[a,b]: D[R[p]]) D[R[i]][a]+=b;
			O[i]+=O[p];
		}
		mn=O[i];
		for(auto[a,b]: D[R[i]]) mn=min(mn,O[i]-=b);
		ans+=mn;
	}
	cout<<ans<<'\n';
	return 0;
}

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