제출 #927553

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
927553		Cutebol	Dreaming (IOI13_dreaming)	C++17	65 / 100	60 ms	13724 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std ;
#define pii pair <int , int>
#define ff first 
#define ss second

const int inf = 1e9 ;
const int N = 1e5 + 5 ;

template <class T>
bool chmax( T& x , const T& y ){
  bool f = 0 ;
  if ( x < y ) x = y , f = 1 ;
  return f ;
}
template <class T>
bool chmin( T &x , const T &y ){
  bool f = 0 ;
  if ( x > y ) x = y , f = 1 ;
  return f ;
}

bool vis[N] ;
int d[N] , f[N] , sc[N] ;
int mx , m , ind , r ;
pii ans[N] ;
vector <pii> g[N] ;

void dfs ( int v , int s , int& m ){
	vis[v] = 1 ; d[v] = s ;
	if ( mx <= d[v] ){
		m = v ; mx = d[v] ;
	}
	for ( auto to : g[v] ) if ( !vis[to.ff] ) dfs(to.ff,s+to.ss,m) ;
}
void fir ( int v , int d , int& m ){
	vis[v] = 0 ; f[v] = d ;
	if ( chmax ( mx , f[v] ) ) m = v ;
	for ( auto to : g[v] ) if ( vis[to.ff] ) fir(to.ff,d+to.ss,m) ;
}
void sec ( int v , int d , int& m ){
	vis[v] = 1 ; sc[v] = d ;
	if ( max( f[v] , sc[v] ) < mx ){
		mx = max ( f[v] , sc[v] ) ; m = v ;
	}
	for ( auto to : g[v] ) if ( !vis[to.ff] ) sec(to.ff,d+to.ss,m) ;
}

int travelTime(int n, int m, int l, int a[], int b[], int c[]) {
    for ( int i = 0 ; i < m ; i ++ ){
		g[a[i]].push_back({b[i],c[i]}) ;
		g[b[i]].push_back({a[i],c[i]}) ;
	}
	if ( m == n-2 ){
		for ( int i = 1 ; i <= n ; i ++ ){
			if ( !vis[i] ){
				mx = 0 ;
				dfs(i,0,m) ;
				mx = 0 ;
				fir(m,0,m) ;
				chmax ( r , f[m] ) ; 
				mx = inf ;
				sec(m,0,m) ;
				ans[ind].ff = f[m] ;
				ans[ind].ss = sc[m] ;
				ind ++ ;
			}
		}
		return max (r,l + max(ans[0].ff,ans[0].ss) + max( ans[1].ff , ans[1].ss )) ;
	}
	if ( n == 1 ) return 0 ;
	if ( n == 2 ){
		if ( m == 1 ) return 0 ;
		return l ;
	}
	vector <int> vec ;
	for ( int i = 0 ; i < m ; i ++ ) vec.push_back(c[i]) ;
	for ( int i = 0 ; i < 5 ; i ++ ) vec.push_back(0) ;
	sort ( vec.rbegin() , vec.rend() ) ;
	return max ( vec[0]+vec[1]+l , vec[1]+vec[2]+2*l ) ;
	
}
/*
signed main(){
	int n , m , l , a[N] , b[N] , t[N] ;
	cin >> n >> m >> l ;
	for ( int i = 0 ; i < m ; i ++ ) cin >> a[i] >> b[i] >> t[i] ;
	cout << travelTime( n , m , l , a , b , t ) ;
}

*/

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23