oj.uz

Submission #520368

# Submission time Handle Problem Language Result Execution time Memory
520368 2022-01-29T16:48:48 Z CaroLinda Worst Reporter 4 (JOI21_worst_reporter4) C++14
0 / 100
 7 ms 5708 KB 
#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) ;
		}

		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] or inDeg[ee] != 0 ) continue ;
				for(auto &y : (*mp[ee])) (*mp[e])[y.ff] += y.ss ;
			}
		}		
		
		for(auto e  : cycle ) inDeg[e] = 0 ;

		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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 2 ms 4940 KB Output is correct
5 Incorrect 7 ms 5708 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 2 ms 4940 KB Output is correct
5 Incorrect 7 ms 5708 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 2 ms 4940 KB Output is correct
5 Incorrect 7 ms 5708 KB Output isn't correct
6 Halted 0 ms 0 KB -