oj.uz

Submission #39758

# Submission time Handle Problem Language Result Execution time Memory
39758 2018-01-18T08:42:35 Z 14kg Beads and wires (APIO14_beads) C++11
0 / 100
 7 ms 4992 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>
#define N 200001
#define INF 999999999999999999

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

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

	if (!check[x][y]) {
		check[x][y] = true;
		if (y) {
			for (auto i : r[x])
				if (i.first != up) {
					long long Push = max2(f(i.first, 1, x) + i.second, f(i.first, 0, x));
					long long 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) {
					long long Push = max2(f(i.first, 1, x) + i.second, f(i.first, 0, x));
					long long 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,(long long)z }), r[y].push_back({ x,(long long)z });
	}
	printf("%lld", 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

# 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 7 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 5 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 7 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 5 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 7 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 5 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 7 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 5 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -