oj.uz

Submission #265553

# Submission time Handle Problem Language Result Execution time Memory
265553 2020-08-15T01:04:40 Z square1001 Beads and wires (APIO14_beads) C++14
28 / 100
 1000 ms 896 KB 
// APIO 2014 Problem 3 - Beads and Wires

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int inf = 2012345678;
int main() {
	// step #1. read input
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> ga(N - 1), gb(N - 1), gw(N - 1);
	for(int i = 0; i < N - 1; ++i) {
		cin >> ga[i] >> gb[i] >> gw[i];
		--ga[i], --gb[i];
	}
	// step #2. construct a graph
	vector<int> sep(N + 1);
	for(int i = 0; i < N - 1; ++i) {
		++sep[ga[i] + 1];
		++sep[gb[i] + 1];
	}
	for(int i = 0; i < N; ++i) {
		sep[i + 1] += sep[i];
	}
	vector<int> ctr(sep);
	vector<int> to(2 * N - 2), cost(2 * N - 2);
	for(int i = 0; i < N - 1; ++i) {
		to[ctr[ga[i]]] = gb[i]; cost[ctr[ga[i]]++] = gw[i];
		to[ctr[gb[i]]] = ga[i]; cost[ctr[gb[i]]++] = gw[i];
	}
	// step #3. calculation (zenhoui-tree-dp part 1)
	vector<int> par(N);
	vector<pair<int, int> > dp1(N);
	function<void(int, int)> solve1 = [&](int pos, int pre) {
		// returns = (no mid-blue, one mid-blue)
		par[pos] = pre;
		int sumcost = 0, delta = -inf;
		for(int i = sep[pos]; i < sep[pos + 1]; ++i) {
			if(to[i] == pre) continue;
			solve1(to[i], pos);
			sumcost += max(dp1[to[i]].first, dp1[to[i]].second + cost[i]);
			delta = max(delta, min(dp1[to[i]].first - dp1[to[i]].second, cost[i]));
		}
		dp1[pos] = make_pair(sumcost, sumcost + delta);
	};
	solve1(0, -1);
	// step #4. calculation (zenhoui-tree-dp part 2)
	vector<pair<int, int> > dp2(N);
	function<void(int, int)> solve2 = [&](int pos, int pre) {
		int sumcost = 0;
		vector<pair<int, int> > deltas;
		for(int i = sep[pos]; i < sep[pos + 1]; ++i) {
			if(to[i] == pre) {
				sumcost += max(dp2[pos].first, dp2[pos].second + cost[i]);
				deltas.push_back(make_pair(min(dp2[pos].first - dp2[pos].second, cost[i]), -1));
			}
			else {
				sumcost += max(dp1[to[i]].first, dp1[to[i]].second + cost[i]);
				deltas.push_back(make_pair(min(dp1[to[i]].first - dp1[to[i]].second, cost[i]), i));
			}
		}
		sort(deltas.begin(), deltas.end(), greater<pair<int, int> >());
		for(int i = sep[pos]; i < sep[pos + 1]; ++i) {
			if(to[i] == pre) continue;
			pair<int, int> dm = make_pair(min(dp1[to[i]].first - dp1[to[i]].second, cost[i]), i);
			int sc = sumcost - max(dp1[to[i]].first, dp1[to[i]].second + cost[i]);
			dp2[to[i]] = make_pair(sc, sc + (dm != deltas[0] ? deltas[0].first : (deltas.size() != 1 ? deltas[1].first : -inf)));
			solve2(to[i], pos);
		}
	};
	dp2[0] = make_pair(0, -inf);
	solve2(0, -1);
	// step #5. calculate and print the answer
	int ans = 0;
	for(int i = 0; i < N; ++i) {
		int sumcost = 0;
		for(int j = sep[i]; j < sep[i + 1]; ++j) {
			if(to[j] == par[i]) {
				sumcost += max(dp2[i].first, dp2[i].second + cost[j]);
			}
			else {
				sumcost += max(dp1[to[j]].first, dp1[to[j]].second + cost[j]);
			}
		}
		ans = max(ans, sumcost);
	}
	for(int i = 0; i < N; ++i) {
		solve1(i, -1);
	}
	cout << ans << endl;
	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 840 ms 656 KB Output is correct
24 Correct 852 ms 760 KB Output is correct
25 Correct 825 ms 760 KB Output is correct
26 Execution timed out 1097 ms 896 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Correct 840 ms 656 KB Output is correct
24 Correct 852 ms 760 KB Output is correct
25 Correct 825 ms 760 KB Output is correct
26 Execution timed out 1097 ms 896 KB Time limit exceeded
27 Halted 0 ms 0 KB -