Submission #947014

#	Time	Username	Problem	Language	Result	Execution time	Memory
947014		vjudge1	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	380 ms	134740 KiB

worst_reporter2

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
long long mainres,n,p[maxn],c[maxn],todor[maxn],vas[maxn];
set<long long>adj[maxn];
set<pair<long long,long long>>dp[maxn];
map<long long,long long>mp;
map<int,int>h[maxn];

void vorod(){
	cin>>n;
	for(long long i=1;i<=n;i++){
		int d;
		cin>>p[i]>>d>>c[i];
		h[i][d]+=c[i];
		mainres+=c[i];
		if(i!=p[i]){
			adj[p[i]].insert(i);
		}
	}
}

void merge(long long u,long long v){
	long long fu=u;
	if((long long)dp[u].size()<(long long)dp[v].size()){
		swap(u,v);
	}
	for(auto x:dp[v]){
		auto y=*dp[u].lower_bound(make_pair(x.first,-1));
		if(y.first==x.first){
			dp[u].erase(y);
			y.second+=x.second;
			dp[u].insert(y);
		}else{
			dp[u].insert(x);
		}
	}
	if(fu!=u){
		swap(dp[u],dp[fu]);
	}
}

void ins(long long u,long long w,long long ww){
	long long moonde=ww;
	while(moonde>0&&(long long)dp[u].size()>0&&(*dp[u].begin()).first<w){
		auto xx=dp[u].lower_bound(make_pair(w,-1));
		xx--;
		auto x=*xx;
		if(x.second>=moonde){
			dp[u].erase(x);
			x.second-=moonde;
			dp[u].insert(x);
			break;
		}else{
			dp[u].erase(x);
			moonde-=x.second;
		}
	}
	if((long long)dp[u].size()==0||(*dp[u].begin()).first>w){
		dp[u].insert(make_pair(w,ww));
		return ;
	}
	auto xx=dp[u].lower_bound(make_pair(w,-1));
	auto x=*xx;
	if(x.first==w){
		dp[u].erase(x);
		x.second+=ww;
		dp[u].insert(x);
	}else{
		dp[u].insert(make_pair(w,ww));
	}
}

void solved(long long u){
	//cout<<"wtf: "<<u<<endl;
	for(auto x:adj[u]){
		solved(x);
		merge(u,x);
	}
	vector<pair<int,int>>insy;
	for(auto x:h[u]){
		insy.push_back(x);
	}
//	reverse(insy.begin(),insy.end());
	for(auto x:insy){
		ins(u,x.first,x.second);
	}
}
deque<int>wtf;

void cald(int u){
	if(vas[u]){
		while((int)wtf.size()>0&&wtf.back()!=u){
			wtf.pop_back();
		}
		return ;
	}
	vas[u]=1;
	wtf.push_front(u);
	cald(p[u]);
}

void pre(){
	for(int i=1;i<=n;i++){
		if(p[i]==i||vas[i]){
			continue;
		}
		cald(i);
		if((int)wtf.size()<=1){
			wtf.clear();
			continue;
		}
		set<int>st;
		for(auto x:wtf){
			st.insert(x);
		}
		int u=wtf.front();
		wtf.pop_front();
		p[u]=u;
		for(auto x:wtf){
			for(auto y:h[x]){
				h[u][y.first]+=y.second;
			}
			for(auto y:adj[x]){
				if(st.count(y)==0){
					adj[u].insert(y);
				}
			}
			adj[u].erase(x);
		}
		wtf.clear();
	}
}

void solve(){
	for(int i=1;i<=n;i++){
		if(p[i]!=i){
			continue;
		}
		solved(i);
		for(auto x:dp[i]){
			mainres-=x.second;
		}
	}
}

void khor(){
	cout<<mainres<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	pre();
//	//cout<<"ha"<<endl;
	solve();
	khor();
}

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