Submission #48043

#	Time	Username	Problem	Language	Result	Execution time	Memory
48043		E869120	Beads and wires (APIO14_beads)	C++14	0 / 100	1069 ms	256 KiB

beads

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N, A[100009], B[100009], C[100009], maxn;

int main() {
	cin >> N;
	for (int i = 0; i < N - 1; i++) { cin >> A[i] >> B[i] >> C[i]; A[i]--; B[i]--; }

	int d[10] = { 0,1,2,3,4,5,6,7,8,9 };

	do {
		int cnt = 0; vector<int>e[10]; bool OK = true;
		for (int i = 0; i < N - 1; i++) {
			if (d[A[i]] < d[B[i]]) e[B[i]].push_back(C[i]); else e[A[i]].push_back(C[i]);
		}
		for (int i = 0; i < N; i++) {
			if (e[i].size() >= 3) OK = false;
			if (e[i].size() == 2) cnt += e[i][0] + e[i][1];
		}
		if (OK == true) maxn = max(maxn, cnt);
	} while (next_permutation(d, d + N));

	cout << maxn << endl;
	return 0;
}

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