Submission #106073

#	Time	Username	Problem	Language	Result	Execution time	Memory
106073		Saboon	Beads and wires (APIO14_beads)	C++14	0 / 100	16 ms	14464 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], DP[maxn], PD[maxn];
vector<pair<int, int> > t[maxn];
vector<int> parmax[maxn], revmax[maxn];

void DFS(int v, int par = -1, int weight = 0, int ord = 0){
	if (par != -1){
		int pdup = dp[par] + DP[par] - max(dp[v], pd[v] + weight);
		int mx = -inf;
		if (ord)
			mx = max(mx, parmax[par][ord - 1]);
		if (ord != t[par].size() - 1)
			mx = max(mx, revmax[par][ord + 1]);
		DP[v] = max(pdup, pdup + mx + weight);
		PD[v] = pdup + weight;
//		cout << "dfs down -> " << v << " -> " << DP[v] << " " << PD[v] << " pdup : " << pdup << endl;
	}
	for (int i = 0; i < t[v].size(); i++){
		auto edge = t[v][i];
		int u = edge.first, c = edge.second;
		if (u != par){
			parmax[v].push_back(dp[u] + c - max(dp[u], pd[u] + c));
			revmax[v].push_back(dp[u] + c - max(dp[u], pd[u] + c));
		}
		else{
			int pdup = dp[par] + DP[par] - max(dp[v], pd[v] + weight);
			int mx = -inf;
			if (ord)
				mx = max(mx, parmax[par][ord - 1]);
			if (ord != t[par].size() - 1)
				mx = max(mx, revmax[par][ord + 1]);
			DP[v] = max(pdup, pdup + mx + weight);
			parmax[v].push_back(pdup + c - max(pdup, pdup + mx + c));
			revmax[v].push_back(pdup + c - max(pdup, pdup + mx + c));
		}
	}
	for (int i = 1; i < t[v].size(); i++)
		parmax[v][i] = max(parmax[v][i], parmax[v][i - 1]);
	for (int i = t[v].size() - 1; i >= 0; i--)
		revmax[v][i] = max(revmax[v][i], revmax[v][i + 1]);

	for (int i = 0; i < t[v].size(); i++){
		auto edge = t[v][i];
		int u = edge.first, c = edge.second;
		if (u != par)
			DFS(u, v, c, i);
	}
}	

void dfs(int v, int par = -1){
	int mx = -inf;
	dp[v] = 0;
	for (int i = 0; i < t[v].size(); i++){
		auto edge = t[v][i];
		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;
//	cout << v << " -> " << dp[v] << " " << pd[v] << endl;
}

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});
	}
	dfs(1);
	DFS(1);
	int answer = 0;
	for (int v = 1; v <= n; v++){
		answer = max(answer, dp[v] + DP[v]);
//		cout << "# " << dp[v] << " " << DP[v] << endl;
	}
	cout << answer << endl;
}

Compilation message (stderr)

beads.cpp: In function 'void DFS(int, int, int, int)':
beads.cpp:20:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ord != t[par].size() - 1)
       ~~~~^~~~~~~~~~~~~~~~~~~~
beads.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < t[v].size(); i++){
                  ~~^~~~~~~~~~~~~
beads.cpp:38:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (ord != t[par].size() - 1)
        ~~~~^~~~~~~~~~~~~~~~~~~~
beads.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < t[v].size(); i++)
                  ~~^~~~~~~~~~~~~
beads.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < t[v].size(); i++){
                  ~~^~~~~~~~~~~~~
beads.cpp: In function 'void dfs(int, int)':
beads.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < t[v].size(); i++){
                  ~~^~~~~~~~~~~~~

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