Submission #1166563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166563		Muhammet	Beads and wires (APIO14_beads)	C++20	28 / 100	1094 ms	8264 KiB

beads

#include "bits/stdc++.h"

using namespace std;

#define ff first
#define ss second
#define ll long long
#define SZ(s) (int)s.size()

const int N = 2e5 + 5;

vector <pair <int, int>> v[N];

ll dp[N][2];

void f(int x, int y) {
	vector <pair <int, int>> v1;
	ll w = 0, s = 0, s1 = 0;
	for(auto i : v[x]) {
		if(i.ff == y) {
			w = i.ss;
			continue;
		}
		f(i.ff, x);
		v1.push_back({i.ff, i.ss});
		s += max(dp[i.ff][0], dp[i.ff][1]);
	}
	dp[x][0] = dp[x][1] = s;
	for(int i = 0; i < SZ(v1); i++) {
		int a = v1[i].ff, wa = v1[i].ss;
		dp[x][1] = max(dp[x][1], w + s - max(dp[a][0], dp[a][1]) + dp[a][0] + wa);
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n;
	cin >> n;
	for(int i = 1; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({b, c});
		v[b].push_back({a, c});
	}

	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		memset(dp, 0, sizeof dp);
		f(i, 0);
		ans = max(ans, dp[i][0]);
	}

	cout << ans;

	return 0;
}

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