Submission #103412

#	Time	Username	Problem	Language	Result	Execution time	Memory
103412		Minnakhmetov	Beads and wires (APIO14_beads)	C++14	0 / 100	4 ms	2688 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 = 1e5 + 5;
vector<E> g[N];
ll dp[N][3];

void dfs(int node, int x, int anc) {
	ll mx1 = -INF, mx2 = -INF, s = 0;
	for (E e : g[node]) {
		if (e.to != anc) {
			dfs(e.to, e.w, node);
			ll a = max(dp[e.to][1], dp[e.to][0]), 
				d = max(dp[e.to][1], dp[e.to][2]) + e.w - a;
			s += a;
			if (mx1 < d) {
				mx2 = mx1;
				mx1 = d;
			}
			else if (mx2 < d) {
				mx2 = d;
			}
		}
	}
	dp[node][2] = s + mx1 + mx2;
	dp[node][1] = s;
	dp[node][0] = s + mx1 + x;
}

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][1], dp[0][2]);

	return 0;
}

Compilation message (stderr)

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

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