Submission #106076

#	Time	Username	Problem	Language	Result	Execution time	Memory
106076		Saboon	Beads and wires (APIO14_beads)	C++14	28 / 100	137 ms	5248 KiB

beads

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 2e5 + 10;
const int inf = 1e8;
 
int dp[maxn], pd[maxn];
vector<pair<int, int> > t[maxn];
 
void dfs(int v, int par = -1){
	int mx = -inf;
	dp[v] = 0;
	for (auto edge : t[v]){
		int u = edge.first, c = edge.second;
		if (u != par){
			dfs(u, v);
			dp[v] += max(dp[u], pd[u] + c);
			mx = max(mx, dp[u] + c - max(dp[u], pd[u] + c)); 
		}
	}
	pd[v] = dp[v] + mx;
}
 
int main(){
	ios_base::sync_with_stdio (false);
	int n;
	cin >> n;
	for (int i = 1; i <= n - 1; i++){
		int v, u, c;
		cin >> v >> u >> c;
		t[v].push_back({u, c});
		t[u].push_back({v, c});
	}
	int answer = 0;
	for (int i = 1; i <= 1000; i++){
		int v = rand() % n + 1;
		dfs(v);
		answer = max(answer, dp[v]);
	}
	cout << answer << endl;
}

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