Submission #387541

#	Time	Username	Problem	Language	Result	Execution time	Memory
387541		idontreallyknow	Beads and wires (APIO14_beads)	C++17	0 / 100	6 ms	8172 KiB

beads

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class A> ostream& operator<<(ostream &cout, vector<A> const &v) {cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";};
template<class A, class B> ostream& operator<<(ostream &cout, const pair<A,B> &x) {return cout << "(" <<x.first << ", " << x.second << ")";};
template <class T> void pv(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) cerr << *i << " "; cerr << "]\n";}
void _print() {cerr << "]\n";}
template <class T, class... V> void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#define fi first
#define se second
#define SZ(x) (int)((x).size())
#define pii pair<ll,ll>
const int mx = 2e5+5;
vector<pii> adj[mx];
int n;
ll dp[mx][2]; //free to put whatever, need to connect parent
void dfs (int v, int p) {
	ll base = 0;
	vector<ll> boost;
	for (pii x : adj[v]) {
		ll a = x.fi, b = x.se;
		if (a == p) continue;
		dfs(a,v);
		if (dp[a][0] == -1) {
			if (dp[a][1] != -1) base += b+dp[a][1];
		} else if (dp[a][1] == -1) {
			base += dp[a][0];
			boost.push_back(b);
		} else {
			ll z = max(dp[a][0], dp[a][1]+b);
			base += z;
			boost.push_back(dp[a][0]+b-z);
		}
	}
	sort(boost.rbegin(), boost.rend());
	dp[v][0] = base;
	if (SZ(boost) >= 2) dp[v][0] = max(dp[v][0], base+boost[0]+boost[1]);
	if (SZ(boost) >= 1) dp[v][1] = base+boost[0];
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int q = 0; q < n-1; q++) {
		ll a,b,c;
		cin >> a >> b >> c;
		adj[a].emplace_back(b,c);
		adj[b].emplace_back(a,c);
	}
	for (int q = 0; q < mx; q++) for (int w = 0; w < 2; w++) dp[q][w] = -1;
	dfs(1,0);
	cout << dp[1][0] << "\n";
	return 0;
}

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