Submission #265539

#	Time	Username	Problem	Language	Result	Execution time	Memory
265539		square1001	Beads and wires (APIO14_beads)	C++14	0 / 100	1 ms	384 KiB

beads

    #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
    	function<pair<int, int>(int, int)> solve = [&](int pos, int pre) {
    		// returns = (no mid-blue, one mid-blue)
    		int sumcost = 0, delta = -inf;
    		for(int i = sep[pos]; i < sep[pos + 1]; ++i) {
    			if(to[i] == pre) continue;
    			pair<int, int> res = solve(to[i], pos);
    			sumcost += max(res.first, res.second + cost[i]);
    			delta = max(delta, min(res.second - res.first, cost[i]));
    		}
    		return make_pair(sumcost, sumcost + delta);
    	};
    	int ans = 0;
    	for(int i = 0; i < N; ++i) {
    		pair<int, int> res = solve(i, -1);
    		ans = max(ans, res.first);
    	}
    	// step #4. print the answer
    	cout << ans << endl;
    	return 0;
    }

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43