Submission #103414

#	Time	Username	Problem	Language	Result	Execution time	Memory
103414		Minnakhmetov	Beads and wires (APIO14_beads)	C++14	100 / 100	401 ms	32364 KiB

beads

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
#pragma warning(disable : 4996)

struct E {
	int to, w;
};

const ll INF = 1e18;
const int N = 2e5 + 5;
vector<E> g[N];
ll dp[N][2][2];

void dfs(int node, int x, int anc) {
	ll mx1 = -INF, mx2 = -INF, mx3 = -INF, s = 0;

	multiset<ll> st;

	for (E e : g[node]) {
		if (e.to != anc) {
			dfs(e.to, e.w, node);
			ll a = max(dp[e.to][0][0], dp[e.to][0][1]);

			mx1 = max(mx1, dp[e.to][0][1] + e.w - a);
			mx2 = max(mx2, max(dp[e.to][0][1], dp[e.to][1][1]) + e.w - a);
			mx3 = max(mx3, max(dp[e.to][1][0], dp[e.to][1][1]) - a);

			s += a;
			
			st.insert(dp[e.to][0][1] + e.w - a);
		}
	}

	dp[node][0][1] = s;
	dp[node][0][0] = s + mx1 + x;
	dp[node][1][0] = s + mx2 + x;
	dp[node][1][1] = s + mx3;

	if (st.size() > 1) {
		for (E e : g[node]) {
			if (e.to != anc) {
				ll a = max(dp[e.to][0][0], dp[e.to][0][1]),
					b = dp[e.to][1][1] + e.w - a,
					c = dp[e.to][0][1] + e.w - a;
				st.erase(st.find(c));
				dp[node][1][1] = max(dp[node][1][1], s + *st.rbegin() + max(b, c));
				st.insert(c);
			}
		}
	}	
}

signed main() {
#ifdef HOME
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	for (int i = 0; i < n - 1; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		x--, y--;
		g[x].push_back({ y, w });
		g[y].push_back({ x, w });
	}

	dfs(0, -1, -1);

	cout << max(dp[0][0][1], dp[0][1][1]);

	return 0;
}

Compilation message (stderr)

beads.cpp:41:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)

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