oj.uz

Submission #625274

# Submission time Handle Problem Language Result Execution time Memory
625274 2022-08-09T18:18:23 Z GusterGoose27 Beads and wires (APIO14_beads) C++11
0 / 100
 4 ms 5032 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 2e5;
int n;
int dp[MAXN][2]; // open, closed
vector<pii> edges[MAXN];
int par_val[MAXN];

struct comp {
	bool operator()(int &a, int &b) {
		return a > b;
	}
} comp;

void dfs(int cur = 0, int p = -1) {
	int o_sum = 0;
	vector<int> diffs;
	for (pii edge: edges[cur]) {
		int next = edge.first;
		if (next == p) continue;
		par_val[next] = edge.second;
		dfs(next, cur);
		o_sum += dp[next][0];
		diffs.push_back(edge.second+dp[next][1]-dp[next][0]);
	}
	sort(diffs.begin(), diffs.end(), comp);
	int ex = 0;
	if (diffs.size() >= 2) ex = diffs[0]+diffs[1];
	dp[cur][1] = max(ex, 0)+o_sum;
	if (diffs.size() == 1 || (diffs.size() >= 2 && par_val[cur] > diffs[1])) ex = diffs[0]+par_val[cur];
	dp[cur][0] = max(ex, 0)+o_sum;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n-1; i++) {
		int x, y, w;
		cin >> x >> y >> w; x--; y--;
		edges[x].push_back(pii(y, w));
		edges[y].push_back(pii(x, w));
	}
	dfs();
	cout << dp[0][1] << "\n";
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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