Submission #667222

#	Time	Username	Problem	Language	Result	Execution time	Memory
667222		manizare	Beads and wires (APIO14_beads)	C++14	0 / 100	1 ms	596 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 = 1e4+100 , maxq =1e5 , inf = 2e18 + 100 , mod = 1e9 + 7 ;
int mark[maxn] ,dp[maxn][2] , par[maxn ];
vector <pair <int , int > > G[maxn] ;
map <pair <int ,int> , int> mp ;

void dfs(int v){
	mark[v] = 1;
	dp[v][0] = 0 ;
	vector <int> vec ;
	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);
		dp[v][0] += max(dp[u][1] , dp[u][0]);
		if(par[v] != 0)
		vec.pb(dp[u][0] + w + mp[{v , par[v]}] - max(dp[u][1] , dp[u][0]));
	}
	sort(all(vec));
	if(vec.size() > 0){
		dp[v][1] = dp[v][0] + vec.back() ;
	}
}

signed main(){	
	int n ;
	cin >> n ;
	for(int i =1 ; i < n ; i++){
		int v, u , w;
		cin >>v >> u >> w ;
		mp[{v ,u }] = mp[{u,v}] =  w;
		G[v].pb({u , w});
		G[u].pb({v , u});
	}
	int ans =0  ; 
	for(int i =1 ;i <= n ;i ++){
		memset(mark , 0 , sizeof mark);
		for(int i = 1;  i <= n ; i++){
			par[i] = 0; 
			dp[i][0] = 0 ; dp[i][1] = -inf ;
		}
		dfs(i);
	//	cout << max(dp[i][1] , dp[i][0]) << "<--\n";
		ans = max(ans , max(dp[i][1] , dp[i][0])); 
	}
	cout << ans << "\n";
}
/*
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:15:20: 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]
   15 |  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