Submission #731168

#	Time	Username	Problem	Language	Result	Execution time	Memory
731168		Cutebol	Beads and wires (APIO14_beads)	C++17	0 / 100	8 ms	14412 KiB

beads

#include <bits/stdc++.h>
   
using namespace std;
#define Nilou ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
#define int long long
#define ff first
#define ss second

const int N = 2e5 + 5 ;
const int mod = 1e9 + 7 ;
const int inf = 1e15 ;

int n , ans , x = inf ;
set <int> d[N] ;
vector <int> g[N] ;
bool vis[N] ;
map < int , map <int , int > > cost ;

void dfs( int v ){
	vis[v] = 1 ;
	for ( auto to : g[v] ) if ( !vis[to] ) dfs(to) ;
	
}

void solve(){
	
	cin >> n ;
	for ( int i = 1 ; i < n ; i ++ ){
		int x , y , c ;
		cin >> x >> y >> c ;
		g[x].push_back(y) ;
		g[y].push_back(x) ;
		cost[x][y] = c ;
		cost[y][x] = c ;
		ans += c ;
	}
	dfs (1) ;
	for ( int i = 1 ; i <= n ; i ++ ) if ( g[i].size() == 1 ) d[g[i][0]].insert(i) ;
	for ( int i = 1 ; i <= n ; i ++ ){
		if ( !d[i].empty() ){
			int a = inf , b = inf ;
			for ( auto j : d[i] ){
				if ( a > b ) swap ( a , b ) ;
				b = min( b , cost[j][i] ) ;
			}
			if ( d[i].size()%2 ) x = min ( x , b ) ;
			else x = min ( x , a+b ) ;
		}
	}
//	cout << x << ' ' << ans << endl ;
	cout << ans - x << endl ;
}

signed main(){
	Nilou ;
	int t = 1 ;
//	cin >> t ;
	while ( t -- ) solve() ;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43