Submission #48045

#	Time	Username	Problem	Language	Result	Execution time	Memory
48045		E869120	Beads and wires (APIO14_beads)	C++14	13 / 100	1075 ms	408 KiB

beads

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

int N, A[100009], B[100009], C[100009], e[10], f[10], g[10][10], 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 {
		for (int i = 0; i < N; i++) { e[i] = 0; f[i] = 0; }
		int cnt = 0; bool OK = true;
		for (int i = 0; i < N - 1; i++) {
			if (d[A[i]] < d[B[i]]) { g[B[i]][e[B[i]]] = A[i]; e[B[i]]++; f[B[i]] += C[i]; }
			else { g[A[i]][e[A[i]]] = B[i]; e[A[i]]++; f[A[i]] += C[i]; }
		}
		for (int i = 0; i < N; i++) {
			if (e[i] >= 3) OK = false;
			if (e[i] == 2 && (e[g[i][0]] >= 1 && e[g[i][1]] >= 1)) OK = false;
			if (e[i] == 2) cnt += f[i];
		}
		if (OK == true) maxn = max(maxn, cnt);
	} while (next_permutation(d, d + N));

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

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