oj.uz

답안 #32029

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
32029 2017-09-23T02:49:07 Z minimario 구슬과 끈 (APIO14_beads) C++14
0 / 100
 4 ms 2688 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
const int MAX = 100005;
typedef pair<int, int> pii;

vector<pii> g[MAX];
int dp[MAX][2][2];

int max(int a, int b, int c) { return max(max(a, b), c); }
int max(int a, int b, int c, int d) { return max(max(a, b), max(c, d)); }

void dfs(int u, int p=-1, int len=-1) {
	for (pii i : g[u]) {
		if (i.f == p) { continue; }
		dfs(i.f, u, i.s);
	}
	int sum = 0, sum2 = 0;
	vector<int> vals;
	for (pii i : g[u]) {
		if (i.f == p) { continue; }
		sum += max(dp[i.f][0][0], dp[i.f][1][0]);
		vals.push_back(max(dp[i.f][0][0], dp[i.f][1][0]) - max(dp[i.f][0][0], dp[i.f][0][1]) - i.s);
	}
	sort(vals.begin(), vals.end());
	if (vals.size() >= 2) {
		dp[u][0][1] = sum - vals[0] - vals[1];
	}
	if (p != -1) {
		for (pii i : g[u]) {
			if (i.f == p) { continue; }
			dp[u][1][0] = max(dp[u][1][0], len + sum - max(dp[i.f][0][0], dp[i.f][1][0]) + dp[i.f][0][0] + i.s);
			dp[u][1][1] = max(dp[u][1][1], len + sum - max(dp[i.f][0][0], dp[i.f][1][0]) + dp[i.f][0][1] + i.s);
		}
	}
	dp[u][0][0] = sum;
	for (pii i : g[u]) {
		if (i.f == p) { continue; }
		dp[u][0][1] = max(dp[u][0][1], sum - max(dp[i.f][0][0], dp[i.f][1][0]) + max(dp[i.f][0][1], dp[i.f][1][1]));
	}
	// cout << u << " " << dp[u][0][0] << " " << dp[u][0][1] << " " << dp[u][1][0] << " " << dp[u][1][1] << endl; 
}
int main() {
	// freopen("a.in", "r", stdin);
	// freopen("a.out", "w", stdout);
	int n; scanf("%d", &n);
	for (int i=0; i<n-1; i++) {
		int u, v, w; scanf("%d %d %d", &u, &v, &w);
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	dfs(1);
	printf("%d\n", max(dp[1][0][0], dp[1][0][1], dp[1][1][0], dp[1][1][1]));
}

Compilation message

beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:20:15: warning: unused variable 'sum2' [-Wunused-variable]
  int sum = 0, sum2 = 0;
               ^~~~
beads.cpp: In function 'int main()':
beads.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n);
         ~~~~~^~~~~~~~~~
beads.cpp:50:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v, w; scanf("%d %d %d", &u, &v, &w);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Incorrect 4 ms 2688 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Incorrect 4 ms 2688 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Incorrect 4 ms 2688 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Incorrect 4 ms 2688 KB Output isn't correct
7 Halted 0 ms 0 KB -