oj.uz

Submission #44740

# Submission time Handle Problem Language Result Execution time Memory
44740 2018-04-06T02:41:35 Z platypus Beads and wires (APIO14_beads) C++17
0 / 100
 9 ms 9600 KB 
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

int N;
vector<pair<int, LL>>graph[234567];
int par[234567];
LL pcost[234567];

void dfs(int v, int las, LL cst) {
	par[v] = las;
	pcost[v] = cst;
	for (auto next : graph[v]) {
		if (next.first == las)continue;
		dfs(next.first, v, next.second);
	}
}

LL memo[2][234567];
LL dp(bool c, int v) {
	if (memo[c][v] >= 0)return memo[c][v];
	LL ans = 0;
	vector<LL>vec;
	for (auto next : graph[v]) {
		int ch = next.first;
		if (ch == par[v])continue;
		LL dpn = dp(0, ch);
		LL dpc = dp(1, ch);
		LL dpv = max(dpc, dpn);
		LL loss = dpn - dpv;
		loss += next.second;
		vec.push_back(loss);
		ans += dpv;
	}
	sort(vec.rbegin(), vec.rend());
	if (c) {
		if (vec.size() > 0) {
			LL can = ans;
			can += vec[0];
			can += pcost[v];
			ans = max(ans, can);
		}
	}
	else {
		if (vec.size() > 1) {
			LL can = ans;
			can += vec[0];
			can += vec[1];
			ans = max(ans, can);
		}
	}
	return memo[c][v] = ans;
}

int main(void)
{
	cin >> N;
	for (int i = 1; i < N; ++i) {
		int u, v; LL cost;
		cin >> u >> v >> cost;
		--u; --v;
		graph[u].push_back({ v,cost });
		graph[v].push_back({ u,cost });
	}
	dfs(0, -1, 0);
	memset(memo, 0xff, sizeof(memo));
	LL ans = dp(0, 0);
	cout << ans << endl;
	return 0;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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