Submission #26612

#	Time	Username	Problem	Language	Result	Execution time	Memory
26612		Bruteforceman	Beads and wires (APIO14_beads)	C++11	100 / 100	500 ms	38888 KiB

beads

#include <bits/stdc++.h>
using namespace std;
int n;
vector <int> g[200010];
vector <int> c[200010];
long long dp[200010][2][2];
const long long inf = 1e16;

void dfs(int x, int par, int parCost) {
	for(size_t i = 0; i < g[x].size(); i++) {
		int y = g[x][i];
		int w = c[x][i];
		if(y == par) continue;
		dfs(y, x, w);
	}
	long long sum;
	vector <long long> best;
	
	// solves 10 case when node x is a middle node
	sum = 0;
	long long t1 = -inf;
	long long t2 = -inf; 
	
	for(size_t i = 0; i < g[x].size(); i++) {
		int y = g[x][i];
		int cost = c[x][i];
		if(y == par) continue;
		long long add = max(dp[y][0][1], dp[y][0][0]);
		sum += add; 
	}
	for(size_t i = 0; i < g[x].size(); i++) {
		int y = g[x][i];
		int cost = c[x][i];
		if(y == par) continue;
		long long add = max(dp[y][0][1], dp[y][0][0]);
		dp[x][1][0] = max(dp[x][1][0], sum + cost + dp[y][1][0] - add + t2);
		dp[x][1][0] = max(dp[x][1][0], sum + cost + dp[y][0][0] - add + t1);
		t1 = max(t1, cost + dp[y][1][0] - add);
		t2 = max(t2, cost + dp[y][0][0] - add);
	}
	// end case
	
	
	// solves 10 case when node x is not a middle node
	sum = 0;
	for(size_t i = 0; i < g[x].size(); i++) {
		int y = g[x][i];
		int cost = c[x][i];
		if(y == par) continue;
		long long add = max(dp[y][0][1], dp[y][0][0]);
		sum += add;
		best.push_back(max(dp[y][1][0], dp[y][1][1]) - add);
	}
	sort(best.begin(), best.end());
	reverse(best.begin(), best.end());
	if(best.size() > 0) dp[x][1][0] = max(dp[x][1][0], sum + best[0]);
	best.clear();
	// end case
	
	
	// solves 11 case
	sum = 0;
	for(size_t i = 0; i < g[x].size(); i++) {
		int y = g[x][i];
		int cost = c[x][i];
		if(y == par) continue;
		long long add = max(dp[y][0][1], dp[y][0][0]);
		sum += add;
		best.push_back(dp[y][1][0] - add + cost);
	}	
	sort(best.begin(), best.end());
	reverse(best.begin(), best.end());
	if(best.size() > 0) {
		dp[x][1][1] = sum + best[0] + parCost;
	} else {
		dp[x][1][1] = -inf;
	}
	best.clear();
	// end case
	
	
	// solves 01 case
	sum = 0;
	for(size_t i = 0; i < g[x].size(); i++) {
		int y = g[x][i];
		int cost = c[x][i];
		if(y == par) continue;
		long long add = max(dp[y][0][0], dp[y][0][1]);
		sum += add;
		best.push_back(dp[y][0][0] - add + cost);
	}
	sort(best.begin(), best.end());
	reverse(best.begin(), best.end());
	if(best.size() > 0) {
		dp[x][0][1] = sum + best[0] + parCost;
	} else {
		dp[x][0][1] = -inf;
	}
	best.clear();
	// end case
	
	// solves 00 case
	sum = 0;
	for(size_t i = 0; i < g[x].size(); i++) {
		int y = g[x][i];
		int cost = c[x][i];
		if(y == par) continue;
		long long add = max(dp[y][0][0], dp[y][0][1]);
		sum += add;
	}
	dp[x][0][0] = sum;
	// end case
}


int main() {
	scanf("%d", &n);
	for(int i = 1; i < n; i++) {
		int p, q, r;
		scanf("%d %d %d", &p, &q, &r);
		g[p].push_back(q);
		g[q].push_back(p);
		c[p].push_back(r);
		c[q].push_back(r);
	}
	dfs(1, 0, 0);
	long long ans = dp[1][1][0];
	printf("%lld\n", ans);	
	// cout << dp[6][1][0] << endl;
	// cout << dp[3][1][0] << endl;
	// cout << dp[2][0][1] << endl;
	// cout << dp[8][1][0] << endl;
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:26:7: warning: unused variable 'cost' [-Wunused-variable]
   int cost = c[x][i];
       ^~~~
beads.cpp:48:7: warning: unused variable 'cost' [-Wunused-variable]
   int cost = c[x][i];
       ^~~~
beads.cpp:106:7: warning: unused variable 'cost' [-Wunused-variable]
   int cost = c[x][i];
       ^~~~
beads.cpp: In function 'int main()':
beads.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &p, &q, &r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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