Submission #104515

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

beads

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

int N, A[10], B[10], C[10], F[10], maxn = 0;

void solve(int G, int H, int I, int dep) {
	maxn = max(maxn, dep);
	vector<pair<int, int>>X[10];
	for (int i = 0; i < N - 1; i++) {
		if ((G / (1 << i)) % 2 == 0) continue;
		X[A[i]].push_back(make_pair(B[i], i));
		X[B[i]].push_back(make_pair(A[i], i));
	}

	for (int i = 0; i < N; i++) {
		if ((I / (1 << i)) % 2 == 0) continue;
		for (int j = 0; j < X[i].size(); j++) {
			for (int k = j + 1; k < X[i].size(); k++) {
				if ((H / (1 << X[i][k].first)) % 2 == 0 && (H / (1 << X[i][j].first)) % 2 == 0) continue;
				int v1 = X[i][j].second, v2 = X[i][k].second;
				solve(G - (1 << v1) - (1 << v2), H & F[i], I & F[i] & F[X[i][j].first] & F[X[i][k].first], dep + C[v1] + C[v2]);
			}
		}
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N - 1; i++) { cin >> A[i] >> B[i] >> C[i]; A[i]--; B[i]--; }
	for (int i = 0; i < N; i++) F[i] = (1 << N) - 1 - (1 << i);
	solve((1 << (N - 1)) - 1, (1 << N) - 1, (1 << N) - 1, 0);
	cout << maxn << endl;
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void solve(int, int, int, int)':
beads.cpp:19:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < X[i].size(); j++) {
                   ~~^~~~~~~~~~~~~
beads.cpp:20:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = j + 1; k < X[i].size(); k++) {
                        ~~^~~~~~~~~~~~~

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