Submission #48035

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

beads

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

int n, a[100009], b[100009], c[100009], maxn;

void dfs(vector<int>v, vector<int>w, int score) {
	for (int i = 0; i < n - 1; i++) {
		if (w[a[i]] == 1 && w[b[i]] == 1 && v[i] == 0) return;
	}
	maxn = max(maxn, score);

	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n - 1; j++) {
			if (v[i] == 1 || v[j] == 1) continue;
			int a1 = -1, a2 = -1, p = -1;
			if (a[i] == a[j]) { a1 = b[i]; a2 = b[j]; p = a[i]; }
			if (a[i] == b[j]) { a1 = b[i]; a2 = a[j]; p = a[i]; }
			if (b[i] == a[j]) { a1 = a[i]; a2 = b[j]; p = b[i]; }
			if (b[i] == b[j]) { a1 = a[i]; a2 = a[j]; p = b[i]; }
			if (a1 == -1 || w[p] == 1) continue;

			vector<int>v1 = v, w1 = w;
			v1[i] = 1; v1[j] = 1;
			w1[p] = 1;
			dfs(v1, w1, score + c[i] + c[j]);
		}
	}
}

int main() {
	// --------------- 13 points solution ---------------
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		cin >> a[i] >> b[i] >> c[i]; a[i]--; b[i]--;
	}
	vector<int>S(n - 1, 0), T(n, 0);
	dfs(S, T, 0);
	cout << maxn << endl;
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(std::vector<int>, std::vector<int>, int)':
beads.cpp:17:17: warning: variable 'a2' set but not used [-Wunused-but-set-variable]
    int a1 = -1, a2 = -1, p = -1;
                 ^~

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