Submission #26598

#	Time	Username	Problem	Language	Result	Execution time	Memory
26598		Bruteforceman	Beads and wires (APIO14_beads)	C++11	57 / 100	601 ms	9948 KiB

beads

#include <bits/stdc++.h>
using namespace std;
int n;
vector <int> g[100010];
vector <int> c[100010];
long long dp[100010][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;
	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++) {
		for(size_t j = 0; j < g[x].size(); j++) {
			if(i == j) continue;
			int p = g[x][i];
			int q = g[x][j];
			int pcost = c[x][i];
			int qcost = c[x][j];
			if(p == par || q == par) continue;
			
			long long opt = pcost + qcost + max(dp[p][1][0] + dp[q][0][0], dp[p][0][0] + dp[q][1][0]);
			long long del = max(dp[p][0][1], dp[p][0][0]) + max(dp[q][0][1], dp[q][0][0]);
			dp[x][1][0] = max(dp[x][1][0], opt + sum - del);
		}
	}
	// 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:23:7: warning: unused variable 'cost' [-Wunused-variable]
   int cost = c[x][i];
       ^~~~
beads.cpp:49:7: warning: unused variable 'cost' [-Wunused-variable]
   int cost = c[x][i];
       ^~~~
beads.cpp:107:7: warning: unused variable 'cost' [-Wunused-variable]
   int cost = c[x][i];
       ^~~~
beads.cpp: In function 'int main()':
beads.cpp:118:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:121: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: 0 / 43