Submission #980571

#	Time	Username	Problem	Language	Result	Execution time	Memory
980571		happy_node	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	289 ms	57452 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=2e5+5;
int N;
int A[MX],H[MX],C[MX];

vector<int> adj[MX];

multiset<pair<ll,ll>> dp[MX];
int par[MX];

int find(int v) {
	return par[v]==v?v:par[v]=find(par[v]);
}

void merge(int u, int v) {
	u=find(u),v=find(v);
	if(u==v) return;

	if(dp[u].size()>dp[v].size()) swap(u,v);

	for(auto [pos,val]:dp[u]) {
		dp[v].insert({pos,val});
	}

	par[u]=v;
	dp[u].clear();
}

void dfs(int v) {
	int prv=-1;
	for(auto u:adj[v]) {
		dfs(u);
		if(prv!=-1) 
			merge(u,prv);
		prv=u;
	}

	if(prv!=-1) merge(v,prv);

	int pv=find(v);

	auto it=dp[pv].lower_bound(make_pair(H[v],0));

	if(it==dp[pv].begin()) {
		dp[pv].insert(make_pair(H[v],C[v]));
	} else {
		it--;
		ll cur=C[v];
		while(true) {
			if(cur>=it->second) {
 				cur-=it->second;
				it=dp[pv].erase(it);
				if(it==dp[pv].begin()) break;
				it--;
			} else {
				auto [p,q]=*it;
				dp[pv].erase(it);
				dp[pv].insert({p,q-cur});
				cur=0;
				break;
			}
		}
		dp[pv].insert(make_pair(H[v],C[v]));
	}
}

int onstk[MX],degs[MX],head[MX];
vector<int> stk;

void dfs0(int v) {
	onstk[v]=1;
	stk.push_back(v);

	if(onstk[A[v]]==0) {
		dfs0(A[v]);
	} else if(onstk[A[v]]==1) {
		vector<int> cyc;
		for(int i=stk.size()-1;i>=0;i--) {
			cyc.push_back(stk[i]);
			if(stk[i]==A[v]) break;
		}

		sort(cyc.begin(),cyc.end(),[&](int i, int j){
			return H[i]>H[j];
		});

		for(int i=0;i+1<cyc.size();i++) {
			head[cyc[i+1]]=cyc[0];
			A[cyc[i]]=cyc[i+1];
		}
		head[cyc[0]]=cyc[0];
		A[cyc.back()]=cyc.back();
	}

	stk.pop_back();
	onstk[v]=2;
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N;
	ll sum=0;
	for(int i=1;i<=N;i++) {
		cin>>A[i]>>H[i]>>C[i];
		sum+=C[i];
	}

	for(int i=1;i<=N;i++) {
		head[i]=i;
		if(onstk[i]==2) continue;
		dfs0(i);
	}

	// for(int i=1;i<=N;i++) {
	// 	cout<<A[i]<<" -> "<<i<<'\n';
	// 	cout<<head[A[i]]<<" "<<head[i]<<'\n';
	// }

	for(int i=1;i<=N;i++) {
		if(A[i]!=i) {
			if(head[A[i]]!=head[i]) {
				adj[head[A[i]]].push_back(head[i]);
				degs[head[i]]+=1;
			} else { 
				adj[A[i]].push_back(i);
				degs[i]+=1;
			}
		}
	}

	for(int i=1;i<=N;i++) par[i]=i;

	ll ans=0;
	for(int i=1;i<=N;i++) {
		if(degs[i]==0) {
			dfs(i);
			for(auto [pos,val]:dp[find(i)]) 
				ans+=val;
		}
	}

	cout<<sum-ans<<'\n';
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'void dfs0(int)':
worst_reporter2.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   for(int i=0;i+1<cyc.size();i++) {
      |               ~~~^~~~~~~~~~~

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