Submission #386298

#	Time	Username	Problem	Language	Result	Execution time	Memory
386298		kshitij_sodani	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	100 / 100	1102 ms	211540 KiB

worst_reporter2

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'


llo n;
llo aa[200001];
llo bb[200001];
llo cc[200001];
vector<llo> adj[2000001];
llo vis[200001];
//llo dp[5001][5001];
map<llo,llo> dp[200001];
vector<llo> adj2[200001];
vector<pair<llo,llo>> val[200001];
llo dfs(llo no,llo par=-1){

	//vis[no]=1;
	//llo cur=cc[no];
	
	vector<llo> tt;
	pair<llo,llo> ma={-1,-1};
	for(auto j:adj[no]){
		if(j!=par){
			//cout<<no<<":"<<j<<endl;
			llo xx=dfs(j,no);
			tt.pb(xx);
			ma=max(ma,{dp[xx].size(),xx});
			//cur+=dp[j][bb[no]];
		}
	}
	if(ma.a==-1){
		if(par==-1){
			map<llo,llo> ap;
			for(auto j:val[no]){
				ap[j.a]+=j.b;
			}
			llo xxx=0;
			for(auto j:ap){
				xxx=max(xxx,j.b);
			}

			return xxx;
		}
		dp[no][0]=0;
		dp[no][bb[no]]=cc[no];
		return no;
	}
	else{
		llo cur=ma.b;
		for(auto j:tt){
			if(j!=cur){
				for(auto i:dp[j]){
					dp[cur][i.a]+=i.b;
				}
			}
		}

		if(par==-1){
			llo ma=0;
			vector<pair<llo,llo>> xx;
			llo su3=0;
			for(auto j:dp[cur]){
				su3+=j.b;
				xx.pb({j.a,su3});
			}
			if(xx.size()){
				ma=max(ma,xx.back().b);
			}
			map<llo,llo> ap;
			for(auto j:val[no]){
				ap[j.a]+=j.b;
			}
			for(auto j:val[no]){
				llo acc=ap[j.a];
				if(xx.size()==0){
					ma=max(ma,acc);
					continue;
				}
				if(xx[0].a>j.a){
					ma=max(ma,acc);
					continue;
				}
				llo ind8=0;
				for(llo i=19;i>=0;i--){
					if((1<<i)+ind8<xx.size()){
						if(xx[(1<<i)+ind8].a<=j.a){
							ind8+=(1<<i);
						}
					}
				}
				ma=max(ma,xx[ind8].b+acc);
			}
			return ma;
		}

		vector<pair<llo,llo>> tt;
		dp[cur][bb[no]]+=cc[no];

		



		auto j=dp[cur].upper_bound(bb[no]);
		llo xx=0;
		vector<llo> yy;
		while(j!=dp[cur].end()){
			xx+=(*j).b;
			if(xx>=cc[no]){
				dp[cur][(*j).a]=xx-cc[no];
				break;
			}
			else{
				yy.pb((*j).a);
			}
			j++;
		}
		for(auto j:yy){
			dp[cur].erase(j);
		}



		return cur;
	}
}
vector<llo> ee;
void dfs2(llo no){
	vis[no]=1;
	for(auto j:adj[no]){
		if(vis[j]==0){
			dfs2(j);
		}
	}
	ee.pb(no);


}

llo ind5=0;
llo coo[200001];

void dfs3(llo no){
	vis[no]=ind5;
	val[ind5].pb({bb[no],cc[no]});
	for(auto j:adj2[no]){
		if(vis[j]==-1){
			dfs3(j);
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	map<llo,llo> ss;
	llo su=0;
	vector<pair<llo,llo>> ed;
	for(llo i=0;i<n;i++){
		cin>>aa[i]>>bb[i]>>cc[i];
		bb[i]=(1000000000+1-bb[i]);
		ss[bb[i]]++;
		aa[i]--;
		if(aa[i]!=i){
			adj[aa[i]].pb(i);

			adj2[i].pb(aa[i]);
			ed.pb({aa[i],i});
		}
		su+=cc[i];
	}
	
	map<llo,llo> tt;
	llo ind=0;
	for(auto j:ss){
		tt[j.a]=ind;
		ind++;
	}	
	for(llo i=0;i<n;i++){
		bb[i]=tt[bb[i]];
	}
	//end compress
	//start scc
	for(llo i=0;i<n;i++){
		if(vis[i]==0){
			dfs2(i);
		}

	}
	

	reverse(ee.begin(),ee.end());

	for(llo i=0;i<n;i++){
		vis[i]=-1;
	}
/*	for(auto j:ee){
		cout<<j<<"<";
	}
	cout<<endl;*/
	for(auto j:ee){
		if(vis[j]==-1){
			ind5=j;
			dfs3(j);
		}
	}
	for(int i=0;i<n;i++){
		adj[i].clear();
	}
	for(auto j:ed){
		if(vis[j.a]!=vis[j.b]){
			adj[vis[j.a]].pb(vis[j.b]);
			//cout<<vis[j.a]<<"::"<<vis[j.b]<<endl;
			coo[vis[j.b]]++;

		}
	}
	//end scc

	
	llo ans=0;
	for(llo i=0;i<n;i++){
		if(coo[i]==0 and vis[i]==i){
			llo co=dfs(i);
			//dfs(i);
			ans+=co;
			//cout<<i<<":"<<co<<endl;
			/*for(auto j:dp[co]){
				ans+=j.b;
			}*/
		}
	}


	cout<<su-ans<<endl;




 
	return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'llo dfs(llo, llo)':
worst_reporter2.cpp:92:20: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |      if((1<<i)+ind8<xx.size()){
      |         ~~~~~~~~~~~^~~~~~~~~~

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