Submission #520367

#	Time	Username	Problem	Language	Result	Execution time	Memory
520367		CaroLinda	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	0 / 100	9 ms	5788 KiB

worst_reporter2

#include <bits/stdc++.h>
 
#define mkt make_tuple
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
#define ll long long
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define pii pair<int,int>
#define mk make_pair
#define ff first
#define ss second
#define tiii tuple<int,int,int>
#define pb push_back

const int MAX  = 2e5+10 ;
const ll inf = 1e18+10LL ;

using namespace std ;

int N ;
int adj[MAX] , val[MAX] , inDeg[MAX] ;
ll cost[MAX] ;
vector<int> rev[MAX] ;
map<int, ll> *mp[MAX] ;

void print(int x){

	cout << x <<": "  << endl ;
	for(auto e : (*mp[x])) cout << e.ff <<" " << e.ss << endl ;
		cout << endl ;

}

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

	vector<int> p ;

	for(int i = 1 ; i <= N ; i++ ) {
		cin >> adj[i] >> val[i] >> cost[i] ;
		p.pb(val[i] ) ;
	}


	sort(all(p) ) ;
	p.erase(unique(all(p) ) , p.end() ) ;

	for(int i = 1 ; i <= N ; i++ ) val[i] = lower_bound(all(p), val[i] )-p.begin()+1 ;
	for(int i = 1 ; i <= N ; i++ ) rev[ adj[i] ].pb(i) ;
	lp(i,1,N+1) inDeg[i] = sz(rev[i]) ;
	lp(i,1,N+1) mp[i] = NULL ;

	queue<int> fila ;
	for(int i= 1 ; i <= N ; i++ )
		if( sz(rev[i] )  == 0 ) fila.push(i) , mp[i] = new map<int,ll>() ;

	while(!fila.empty() ){
		int x = fila.front() ;
		fila.pop() ;
		
		for(auto e : rev[x] ){
			if( mp[e] == mp[x] ) continue ;
			for(auto &ee : (*mp[e]) ) (*mp[x])[ee.first] += ee.second ;
			(*mp[e]).clear() ;
		}

		(*mp[x])[1] += cost[x] ;
		(*mp[x])[val[x]] -= cost[x] ;
		(*mp[x])[val[x]+1] += cost[x] ;

		auto it = (*mp[x]).find(val[x] ) ;
		while(it != (*mp[x]).begin() && it->second < cost[x] ){
			ll s = it->second ;
			it = (*mp[x]).erase(it) ;
			it-- ;
			it->second += s ;
		} 

		if( mp[adj[x]] == NULL ) mp[adj[x]]=mp[x] ;
		if( sz( (*mp[x]) ) > sz( (*mp[adj[x]])) ) mp[adj[x] ] = mp[x] ;

		if( (--inDeg[adj[x]] ) == 0 ) fila.push(adj[x]) ;

	}

	ll ans = 0 ;

	for(int i= 1 ; i <= N ; i++ ){
		if(inDeg[i] == 0 ) continue ;

		vector<int> cycle = {i, adj[i]} ;
		while(cycle.back() != cycle[0] ){
			int aux = adj[ cycle.back() ] ;
			cycle.pb(aux) ;
		}

		for(auto e : cycle ) inDeg[e] = 0 ;

		cycle.pop_back() ;

		for(auto e : cycle ){
			if( mp[e] == NULL ) mp[e] = new map<int,ll>() ;
			(*mp[e] )[1] += cost[e] ;
			(*mp[e])[val[e]] -= cost[e] ;
			(*mp[e])[val[e]+1] += cost[e] ;
			for(auto ee : rev[e]){
				if(mp[e]  == mp[ee]) continue ;
				for(auto &y : (*mp[ee])) (*mp[e])[y.ff] += y.ss ;
			}
		}		
		
		for(int i= 1 ; i< sz(cycle) ; i++ )
			for(auto e : (*mp[cycle[i]] ) ) (*mp[cycle[0]])[e.ff] += e.ss ;


		ll curMin = inf ;
		ll cur = 0 ;

		for(auto e : (*mp[cycle[0]]) ){
			cur += e.ss ;
			curMin = min(curMin, cur) ;
		}

		ans += curMin ;

	}

	cout << ans <<"\n" ;

}

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