Submission #347094

#	Time	Username	Problem	Language	Result	Execution time	Memory
347094		negar_a	Beads and wires (APIO14_beads)	C++14	0 / 100	4 ms	5100 KiB

beads

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 2e5 + 10;
vector <pii> adj[maxn];
int dp[5][maxn];
int inf = 1e5;
//dp[0][u] = max gain age u too hish gilasi vasat nabashe!
//dp[1][u] = max gain age u bein pedar o yeki az bache hash bashe
//dp[2][u] = max gain age u bein do ta az bache hash bashe 
//ans = max(dp[0 , 2][0]) !

void dfs(int u, int p = -1){
	int mx1 = -inf, mx2 = -inf;
	for(auto i : adj[u]){
		int v = i.F;
		if(v != p){
			dfs(v, u);
			if(dp[1][v])
				dp[1][v] += i.S;
				
			dp[0][u] += dp[1][v];
			
			int x = max(dp[0][v], dp[2][v]);
			x += i.S;
				 
			if(mx1 < (x - dp[1][v])){
				mx2 = mx1;
				mx1 = (x - dp[1][v]);
			}else if(mx2 < (x - dp[1][v])){
				mx2 = (x - dp[1][v]);
			}
		}
	}
	dp[1][u] = dp[2][u] = dp[0][u];
	dp[1][u] = (adj[u].size() > 1 || u == 0) ? dp[1][u] + mx1 : 0;
	dp[2][u] += ((int)adj[u].size() > 2 || u == 0 && adj[u].size() > 1) ? mx2 + mx1 : 0;
//	cout << u + 1 << " " << dp[0][u] << " " << dp[1][u] << " " << dp[2][u] << " | " << mx1 << " " << mx2 << " !!! " << endl;
}

int main(){
	fast_io;
	int n;
	cin >> n;
	for(int i = 0; i < n - 1; i ++){
		int a, b, c;
		cin >> a >> b >> c;
		a --; b --;
		adj[a].pb({b, c});
		adj[b].pb({a, c});	
	}
	dfs(0);
	cout << max({dp[0][0], dp[2][0]});
	
	return 0;
}
/*
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(int, int)':
beads.cpp:46:48: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   46 |  dp[2][u] += ((int)adj[u].size() > 2 || u == 0 && adj[u].size() > 1) ? mx2 + mx1 : 0;
      |                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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