Submission #666776

#	Time	Username	Problem	Language	Result	Execution time	Memory
666776		manizare	Beads and wires (APIO14_beads)	C++14	0 / 100	9 ms	14480 KiB

beads

#include <bits/stdc++.h>
#define all(a) a.begin(),a.end() 
#define pb push_back
#define int long long 
using namespace std ;
const int maxn = 2e5 + 1000 , maxq =1e5 , inf = 1e18 + 100 , mod = 1e9 + 7 ;
int mark[maxn] , dp[maxn][3] , par[maxn];
map <int , int> m[maxn]; 
vector <pair <int ,int > > G[maxn] ;

void dfs(int v){
	mark[v] =1 ;
	if(v==4){
	//	cout << G[v].size() << " " << par[v] << "<--\n";
	}
	if(G[v].size() >= 2 && par[v] !=0 ){
		dp[v][1] = m[v][par[v]] ;
	}else{
		dp[v][1] = -inf ;
	}
	vector <int> vec;int sum =0  ; 
	for(int i =0 ; i < G[v].size() ; i++){
		int u = G[v][i].first , w = G[v][i].second ;
		if(mark[u] ==1 )continue ;
		par[u] = v; 
		dfs(u);
		sum += max(dp[u][0] , dp[u][1]) ;
		vec.pb(dp[u][0]+ w - max(dp[u][0] , dp[u][1])) ;
	}
	if(v == 4){
//		cout << sum << "<----------------------------\n";
	}
	dp[v][0] = sum ;
	sort(all(vec));
	reverse(all(vec));
	if(vec.size() >= 1){
		dp[v][1] += sum + vec[0] ;
	}
	if(vec.size() >= 2){
		dp[v][0] = max(dp[v][0] , sum + vec[0] + vec[1]); 
	}
//	cout << v << " : " << dp[v][0] << " " << dp[v][1] << "<--\n";
}

 
signed main(){
	int n ;
	cin >> n ;
	for(int i = 1; i < n ; i++){
		int v , u , w;
		cin >> v >> u >> w ;
		G[v].pb({u,w});
		m[v][u] = m[u][v] = w ;
		G[u].pb({v,w});
	}
	dfs(1);
	cout << max(dp[1][0] , dp[1][1]) ;
}
/*

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5 
2 4 3
2 5 8
1 6 55
6 8 34
*/

Compilation message (stderr)

beads.cpp: In function 'void dfs(long long int)':
beads.cpp:22:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i =0 ; i < G[v].size() ; i++){
      |                 ~~^~~~~~~~~~~~~

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