oj.uz

Submission #26591

# Submission time Handle Problem Language Result Execution time Memory
26591 2017-07-03T11:49:47 Z Bruteforceman Beads and wires (APIO14_beads) C++11
0 / 100
 6 ms 4992 KB 
#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; 
		best.push_back(dp[y][1][0] - add + cost);
	}
	sort(best.begin(), best.end());
	reverse(best.begin(), best.end());
	if(best.size() > 1) dp[x][1][0] = max(dp[x][1][0], sum + best[0] + best[1]);
	best.clear();
	// 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[8][1][0] << endl;
	return 0;
}

Compilation message

beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:40:7: warning: unused variable 'cost' [-Wunused-variable]
   int cost = c[x][i];
       ^~~~
beads.cpp:98:7: warning: unused variable 'cost' [-Wunused-variable]
   int cost = c[x][i];
       ^~~~
beads.cpp: In function 'int main()':
beads.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:112: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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Incorrect 6 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Incorrect 6 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Incorrect 6 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Incorrect 6 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -