Submission #386293

#	Time	Username	Problem	Language	Result	Execution time	Memory
386293		model_code	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	375 ms	76944 KiB

worst_reporter2

// O(N(logN)^2)

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<int> vi;

void dfs(int v,map<int,ll> &mp,vector<vi> &g,vi &H,vi &C){
	for(auto u:g[v]){
		map<int,ll> mp_;
		dfs(u,mp_,g,H,C);
		if(mp.size()<mp_.size()) mp.swap(mp_);
		for(auto p:mp_) mp[p.first]+=p.second;
	}
	mp[H[v]]+=C[v];
	ll t=C[v];
	while(t){
		auto p=mp.upper_bound(H[v]);
		if(p==mp.end()) break;
		ll sa=min(p->second,t);
		p->second-=sa;
		t-=sa;
		if(p->second==0) mp.erase(p);
	}
}

ll Solve(int N,vi A,vi H,vi C){
	vector<vi> g(N);
	ll res=0;
	for(int i=1;i<N;i++) g[A[i]].push_back(i);
	for(int i=0;i<N;i++) H[i]*=-1;
	for(auto i:C) res+=i;
	map<int,ll> mp;
	dfs(0,mp,g,H,C);
	for(auto p:mp) res-=p.second;
	return res;
}

int N;
vi A,H,C;

int main(){
	scanf("%d",&N);
	A=H=C=vi(N);
	vi deg(N),ind(N,-1);
	vector<vi> g(N);
	queue<int> q;
	ll res=0;
	for(int i=0;i<N;i++){
		scanf("%d%d%d",&A[i],&H[i],&C[i]);
		A[i]--;
		deg[A[i]]++;
		g[A[i]].push_back(i);
	}
	for(int i=0;i<N;i++) if(!deg[i]) q.push(i);
	while(!q.empty()){
		int v=q.front(),u=A[v];
		q.pop();
		deg[u]--;
		if(!deg[u]) q.push(u);
	}
	for(int i=0;i<N;i++) if(ind[i]<0&&deg[i]){
		int v=i,I=1;
		vector<pair<int,int>> b;
		do{
			b.push_back({H[v],C[v]});
			ind[v]=0;
			for(auto u:g[v]) if(!deg[u]){
				ind[u]=I++;
				q.push(u);
			}
			v=A[v];
		}while(v!=i);
		sort(b.rbegin(),b.rend());
		int N_=(int)b.size();
		vi A_(N_),H_,C_;
		for(int i=1;i<N_;i++) A_[i]=i-1;
		for(auto p:b){
			H_.push_back(p.first);
			C_.push_back(p.second);
		}
		while(!q.empty()){
			int u=q.front();
			q.pop();
			A_.push_back(ind[A[u]]+N_-1);
			H_.push_back(H[u]);
			C_.push_back(C[u]);
			for(auto w:g[u]){
				ind[w]=I++;
				q.push(w);
			}
		}
		N_=A_.size();
		res+=Solve(N_,A_,H_,C_);
	}
	printf("%lld\n",res);
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |  scanf("%d",&N);
      |  ~~~~~^~~~~~~~~
worst_reporter2.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |   scanf("%d%d%d",&A[i],&H[i],&C[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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