답안 #26605 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
26605	2017-07-03T12:44:31 Z	Bruteforceman	구슬과 끈 (APIO14_beads)	C++11	57 / 100	1000 ms	36348 KB

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;
	vector < pair <long long, int> > t1, t2; 
	
	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; 
		t1.emplace_back(cost + dp[y][1][0] - add, y);
		t2.emplace_back(cost + dp[y][0][0] - add, y);
	}
	/*
	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);
		}
	}
	*/
	sort(t1.begin(), t1.begin());
	sort(t2.begin(), t2.end());
	reverse(t1.begin(), t1.end());
	reverse(t2.begin(), t2.end());
	if(t1.size() > 1) {
		for(int i = 0; i < t1.size(); i++) {
			for(int j = 0; j < t2.size(); j++) {
				if(t1[i].second != t2[j].second) dp[x][1][0] = max(dp[x][1][0], sum + t1[i].first + t2[j].first);
			}
		}
	}
	t1.clear();
	t2.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[3][1][0] << endl;
	// cout << dp[2][0][1] << endl;
	// cout << dp[8][1][0] << endl;
	return 0;
}

Compilation message

beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < t1.size(); i++) {
                  ~~^~~~~~~~~~~
beads.cpp:54:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j < t2.size(); j++) {
                   ~~^~~~~~~~~~~
beads.cpp:68:7: warning: unused variable 'cost' [-Wunused-variable]
   int cost = c[x][i];
       ^~~~
beads.cpp:126:7: warning: unused variable 'cost' [-Wunused-variable]
   int cost = c[x][i];
       ^~~~
beads.cpp: In function 'int main()':
beads.cpp:137:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:140: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.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	9728 KB	Output is correct
2	Correct	10 ms	9728 KB	Output is correct
3	Correct	9 ms	9728 KB	Output is correct
4	Correct	10 ms	9728 KB	Output is correct
5	Correct	11 ms	9728 KB	Output is correct
6	Correct	10 ms	9728 KB	Output is correct
7	Correct	10 ms	9740 KB	Output is correct
8	Correct	10 ms	9728 KB	Output is correct
9	Correct	10 ms	9724 KB	Output is correct
10	Correct	15 ms	9728 KB	Output is correct
11	Correct	10 ms	9700 KB	Output is correct
12	Correct	10 ms	9728 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	9728 KB	Output is correct
2	Correct	10 ms	9728 KB	Output is correct
3	Correct	9 ms	9728 KB	Output is correct
4	Correct	10 ms	9728 KB	Output is correct
5	Correct	11 ms	9728 KB	Output is correct
6	Correct	10 ms	9728 KB	Output is correct
7	Correct	10 ms	9740 KB	Output is correct
8	Correct	10 ms	9728 KB	Output is correct
9	Correct	10 ms	9724 KB	Output is correct
10	Correct	15 ms	9728 KB	Output is correct
11	Correct	10 ms	9700 KB	Output is correct
12	Correct	10 ms	9728 KB	Output is correct
13	Correct	10 ms	9728 KB	Output is correct
14	Correct	10 ms	9728 KB	Output is correct
15	Correct	10 ms	9728 KB	Output is correct
16	Correct	9 ms	9728 KB	Output is correct
17	Correct	10 ms	9728 KB	Output is correct
18	Correct	9 ms	9728 KB	Output is correct
19	Correct	10 ms	9728 KB	Output is correct
20	Correct	9 ms	9728 KB	Output is correct
21	Correct	10 ms	9728 KB	Output is correct
22	Correct	10 ms	9728 KB	Output is correct

Subtask #3
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	9728 KB	Output is correct
2	Correct	10 ms	9728 KB	Output is correct
3	Correct	9 ms	9728 KB	Output is correct
4	Correct	10 ms	9728 KB	Output is correct
5	Correct	11 ms	9728 KB	Output is correct
6	Correct	10 ms	9728 KB	Output is correct
7	Correct	10 ms	9740 KB	Output is correct
8	Correct	10 ms	9728 KB	Output is correct
9	Correct	10 ms	9724 KB	Output is correct
10	Correct	15 ms	9728 KB	Output is correct
11	Correct	10 ms	9700 KB	Output is correct
12	Correct	10 ms	9728 KB	Output is correct
13	Correct	10 ms	9728 KB	Output is correct
14	Correct	10 ms	9728 KB	Output is correct
15	Correct	10 ms	9728 KB	Output is correct
16	Correct	9 ms	9728 KB	Output is correct
17	Correct	10 ms	9728 KB	Output is correct
18	Correct	9 ms	9728 KB	Output is correct
19	Correct	10 ms	9728 KB	Output is correct
20	Correct	9 ms	9728 KB	Output is correct
21	Correct	10 ms	9728 KB	Output is correct
22	Correct	10 ms	9728 KB	Output is correct
23	Correct	14 ms	10240 KB	Output is correct
24	Correct	15 ms	10240 KB	Output is correct
25	Correct	15 ms	10240 KB	Output is correct
26	Correct	20 ms	10692 KB	Output is correct
27	Correct	25 ms	10752 KB	Output is correct
28	Correct	247 ms	11392 KB	Output is correct
29	Correct	121 ms	10912 KB	Output is correct
30	Correct	103 ms	11092 KB	Output is correct
31	Correct	67 ms	11896 KB	Output is correct

Subtask #4
0 / 43.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	9728 KB	Output is correct
2	Correct	10 ms	9728 KB	Output is correct
3	Correct	9 ms	9728 KB	Output is correct
4	Correct	10 ms	9728 KB	Output is correct
5	Correct	11 ms	9728 KB	Output is correct
6	Correct	10 ms	9728 KB	Output is correct
7	Correct	10 ms	9740 KB	Output is correct
8	Correct	10 ms	9728 KB	Output is correct
9	Correct	10 ms	9724 KB	Output is correct
10	Correct	15 ms	9728 KB	Output is correct
11	Correct	10 ms	9700 KB	Output is correct
12	Correct	10 ms	9728 KB	Output is correct
13	Correct	10 ms	9728 KB	Output is correct
14	Correct	10 ms	9728 KB	Output is correct
15	Correct	10 ms	9728 KB	Output is correct
16	Correct	9 ms	9728 KB	Output is correct
17	Correct	10 ms	9728 KB	Output is correct
18	Correct	9 ms	9728 KB	Output is correct
19	Correct	10 ms	9728 KB	Output is correct
20	Correct	9 ms	9728 KB	Output is correct
21	Correct	10 ms	9728 KB	Output is correct
22	Correct	10 ms	9728 KB	Output is correct
23	Correct	14 ms	10240 KB	Output is correct
24	Correct	15 ms	10240 KB	Output is correct
25	Correct	15 ms	10240 KB	Output is correct
26	Correct	20 ms	10692 KB	Output is correct
27	Correct	25 ms	10752 KB	Output is correct
28	Correct	247 ms	11392 KB	Output is correct
29	Correct	121 ms	10912 KB	Output is correct
30	Correct	103 ms	11092 KB	Output is correct
31	Correct	67 ms	11896 KB	Output is correct
32	Correct	80 ms	14456 KB	Output is correct
33	Correct	76 ms	14572 KB	Output is correct
34	Correct	84 ms	14584 KB	Output is correct
35	Correct	404 ms	29012 KB	Output is correct
36	Correct	390 ms	29032 KB	Output is correct
37	Correct	400 ms	29016 KB	Output is correct
38	Execution timed out	1077 ms	36348 KB	Time limit exceeded
39	Halted	0 ms	0 KB	-

답안 #26605

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 15.0 / 15.0

Subtask #3 29.0 / 29.0

Subtask #4 0 / 43.0

Subtask #1
13.0 / 13.0

Subtask #2
15.0 / 15.0

Subtask #3
29.0 / 29.0

Subtask #4
0 / 43.0