oj.uz

답안 #39756

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39756 2018-01-18T08:13:05 Z 14kg 구슬과 끈 (APIO14_beads) C++11
0 / 100
 5 ms 4992 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>
#define N 200001
#define INF 1000000000

using namespace std;
int n, dp[N][2];
bool check[N][2];
vector<pair<int, int> > r[N];

int max2(int x, int y) { return x > y ? x : y; }
int f(int x, int y, int up) {
	int MAX1 = -INF, MAX2 = -INF;

	if (!check[x][y]) {
		check[x][y] = true;
		if (y) {
			for (auto i : r[x])
				if (i.first != up) {
					int Push = max2(f(i.first, 1, x) + i.second, f(i.first, 0, x));
					int temp = i.second + f(i.first, 0, x) - Push;
					if (MAX1 < temp) MAX1 = temp;
					dp[x][y] += Push;
				}
			dp[x][y] += MAX1;
		}
		else {
			for (auto i : r[x])
				if (i.first != up) {
					int Push = max2(f(i.first, 1, x) + i.second, f(i.first, 0, x));
					// if (x == 1 && y == 0) printf(" >> %d %d %d\n",i.first ,Push, i.second + f(i.first, 0, x) - Push);
					int temp = i.second + f(i.first, 0, x) - Push;
					if (MAX1 < temp) MAX2 = MAX1, MAX1 = temp;
					else if (MAX2 < temp) MAX2 = temp;
					dp[x][y] += Push;
				}
			dp[x][y] += max2(0, MAX1 + MAX2);
		}
	} return dp[x][y];
}
int main() {
	int x, y, z;

	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		scanf("%d %d %d", &x, &y, &z);
		r[x].push_back({ y,z }), r[y].push_back({ x,z });
	}
	printf("%d", f(1, 0, 0));
}

Compilation message

beads.cpp: In function 'int main()':
beads.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &x, &y, &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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