Submission #262402

#	Time	Username	Problem	Language	Result	Execution time	Memory
262402		youssefbou62	Wiring (IOI17_wiring)	C++14	0 / 100	184 ms	49128 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define sz(x)	(int)x.size()
#define ll long long  
#define pb push_back 
#define all(x) x.begin(),x.end()
#define fi first 
#define se second 
using namespace std; 

const int MAXN = 2e5+1 ;
unordered_map<int,ll> dp[MAXN];  
vector<int> adj[MAXN],adj1[MAXN]; 
int R,B; 
void mins(ll& a ,ll b ){
	a = min ( a , b ) ; 
}
vector<int> rr , bb ; 
 
ll solve (int i ,int u ){
	// if( j >= sz(adj[i]) )return 1e18 ; 
	// int u = adj[i][j] ; 
	if( lower_bound(all(adj[i]),u) == adj[i].end() )
		u = adj[i][0];  

	if( i == R && u == B ){
		return 0 ; 
	}
	// cout << i << " " << j << endl; 

	if( dp[i].count(u) )
		return dp[i][u] ;
	ll& r = dp[i][u] ;
	r = 1e18 ;  
	if( i < R && u < B){ 
		int y = *upper_bound(all(adj[i+1]),u); 
		r = min(r,solve(i+1,y)+1LL*abs( rr[i] - bb[u] ) ); 
	}
	// cout << i << " *******" << u << endl; 
	if( u < B ){
		for(int x : adj1[u]){ 
			if( x >= i )continue ;
			int y = *upper_bound(all(adj[i]),u); 
			r = min(r,solve(i,y)+1LL*abs(rr[x]-bb[u])); 
		}
	}
	// cout << i << " *******" << u << endl; 
	if( i < R )
	for(int k = 0 ; k < sz(adj[i]) ; k++ ){
		int v = adj[i][k] ;
		if( v >= u )break ; 
		r = min(r,solve(i+1,u)+1LL*abs(rr[i]-bb[v])); 
	}
	// cout << i << " " << u << " " << r << endl; 
	return r; 
}

long long min_total_length(vector<int> r, vector<int> b) {
	rr = r ; 
	bb =b ; 
	 R = sz(r) , B = sz(b) ;
	vector<pair<int,int>> connections; 
	for(int i = 0 ; i < R ; i++ ){
		connections.pb({r[i],-i-1}); 
	}
	for(int i = 0 ; i < B ; i++ ){
		connections.pb({b[i],i+1}); 
	}
	sort(all(connections));  
	for(int i = 0 ; i < sz(connections); i++ ){
		if(connections[i].se < 0 ){ 
			for(int j = i - 6 ; j <= i + 6 && j<sz(connections) ; j++ ){
				if( j < 0  )continue  ; 
				if( connections[j].se < 0 )continue ; 
				adj[-connections[i].se-1].pb(connections[j].se-1); 
		}	
		}else{
			for(int j = i - 6 ; j <= i + 6 && j<sz(connections) ; j++ ){
				if( j < 0  )continue  ; 
				if( connections[j].se > 0 )continue ; 
				adj1[connections[i].se-1].pb(-connections[j].se-1); 
			}
	
		}
	}for(int i=0 ; i< R; i++ ){
		sort(all(adj[i]));
		adj[i].pb(B);  
	}
	adj[R] = adj[R-1]; 
	
	
	return solve(0,adj[0][0]) ; 
}



 // int main() {
 // 	int n, m;
 // 	assert(2 == scanf("%d %d", &n, &m));

 // 	vector<int> r(n), b(m);
 // 	for(int i = 0; i < n; i++)
 // 		assert(1 == scanf("%d", &r[i]));
 // 	for(int i = 0; i < m; i++)
 // 		assert(1 == scanf("%d", &b[i]));

 // 	long long res = min_total_length(r, b);
 // 	printf("%lld\n", res);

 // 	return 0;
 // }
	// 

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45