Submission #94854

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

beads

//Smaug never desolated!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)1e5 + 3;
const int MAXS = (int)203;
const int MOD = (int)1e9 + 7;
const int infint = (int)1e9;
const ll inf = (ll)1e15;
int n, k, dp1[MAXN], dp2[MAXN];
vector<pair<int, int> > G[MAXN];
void dfs(int u, int p)
{
	int childs = 0;
	for (auto v : G[u])
		if(v.first != p)
			dfs(v.first, u), childs++;
	if(childs == 0)
	{
		dp1[u] = 0, dp2[u] = -infint;
		return;
	}
	//dp1
	for (auto v : G[u])
		if(v.first != p)
			dp1[u] += max(dp1[v.first], dp2[v.first] + v.second);
	int mx1 = -infint, mx2 = -infint, ans1 = 0, ans2 = 0;
	for (auto v : G[u])
		if(v.first != p)
			if(dp1[v.first] + v.second - max(dp2[v.first] + v.second, dp1[v.first]) > mx1)
				mx2 = mx1, ans2 = ans1, mx1 = dp1[v.first] + v.second - max(dp2[v.first] + v.second, dp1[v.first]), ans1 = v.first;
			else
			if(dp1[v.first] + v.second - max(dp2[v.first] + v.second, dp1[v.first]) > mx2)
				mx2 = dp1[v.first] + v.second - max(dp2[v.first] + v.second, dp1[v.first]), ans2 = v.first;
	dp1[u] += max(0, mx1 + mx2);
	//dp2
	int sum = 0;
	for (auto v : G[u])
		if(v.first != p)
			sum += max(dp2[v.first] + v.second, dp1[v.first]);
	for (auto v : G[u])
		if(v.first != p)
			dp2[u] = max(dp2[u], sum + dp1[v.first] + v.second - max(dp2[v.first] + v.second, dp1[v.first]));
	return;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		G[u].push_back({v, w});
		G[v].push_back({u, w});
	}
	dfs(1, -1);
	cout << dp1[1];
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:30:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   if(v.first != p)
     ^
beads.cpp:28:46: warning: variable 'ans2' set but not used [-Wunused-but-set-variable]
  int mx1 = -infint, mx2 = -infint, ans1 = 0, ans2 = 0;
                                              ^~~~

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