oj.uz

Submission #731174

# Submission time Handle Problem Language Result Execution time Memory
731174 2023-04-27T06:22:18 Z Cutebol Beads and wires (APIO14_beads) C++17
0 / 100
 7 ms 14292 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 14292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 14292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 14292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 14292 KB Output isn't correct
2 Halted 0 ms 0 KB -