Submission #100181

#	Time	Username	Problem	Language	Result	Execution time	Memory
100181		Plurm	Beads and wires (APIO14_beads)	C++11	0 / 100	6 ms	4992 KiB

beads

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

vector<pair<int,int> > g[200005];
long long dp[200005][2];
void dfs(int u, int p = -1){
	vector<pair<int,int> > vec;
	dp[u][1] = 0ll;
	long long smx = -1e12;
	long long mx = -1e12;
	int ccnt = 0;
	for(auto v : g[u]){
		if(v.first == p) continue;
		dfs(v.first, u);
		// Choice 1
		long long x = max(dp[v.first][0], dp[v.first][1] + v.second);
		// Choice 2
		long long y = dp[v.first][0] + v.second;
		if(y - x > mx){
			smx = mx;
			mx = y - x;
		}else if(y - x > smx){
			smx = y - x;
		}
		dp[u][0] += x;
		dp[u][1] += x;
		ccnt++;
	}
	if(ccnt >= 2){
		if(mx + smx >= 0ll) dp[u][0] += mx + smx;
	}
	if(ccnt >= 1){
		dp[u][1] += mx;
	}else{
		dp[u][1] = -1e12;
	}
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1; i < n; i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		g[a].emplace_back(b,c);
		g[b].emplace_back(a,c);
	}
	dfs(1);
	printf("%lld\n",dp[1][0]);
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
beads.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a,&b,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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