Submission #104517

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

beads

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

int N, A[100009], B[100009], C[100009], F[100009], 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 + 1] - 1].push_back(make_pair(B[i + 1] - 1, i));
		X[B[i + 1] - 1].push_back(make_pair(A[i + 1] - 1, 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 + 1] + C[v2 + 1]);
			}
		}
	}
}

int solve_Jury() {
	maxn = 0;
	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);
	return maxn;
}

vector<pair<int, int>>X[100009], Y[100009]; int par[100009], w[100009], dp[100009][4];
bool used[100009];

void init() {
	for (int i = 0; i < 19; i++) {
		X[i].clear(); Y[i].clear();
		par[i] = 0; w[i] = 0; used[i] = false;
		for (int j = 0; j < 4; j++) dp[i][j] = 0;
	}
}

void dfs1(int pos) {
	used[pos] = true;
	for (int i = 0; i < X[pos].size(); i++) {
		if (used[X[pos][i].first] == true) continue;
		par[X[pos][i].first] = pos;
		w[X[pos][i].first] = X[pos][i].second;
		Y[pos].push_back(X[pos][i]);
		dfs1(X[pos][i].first);
	}
}

void dfs2(int pos) {
	for (int i = 0; i < Y[pos].size(); i++) dfs2(Y[pos][i].first);

	// pos を中心に結ばない場合
	for (int i = 0; i < Y[pos].size(); i++) {
		dp[pos][0] += max({ dp[Y[pos][i].first][0], dp[Y[pos][i].first][1], dp[Y[pos][i].first][2], dp[Y[pos][i].first][3] });
	}

	// pos を中心に結ぶ場合
	for (int i = 0; i < X[pos].size(); i++) {
		for (int j = i + 1; j < X[pos].size(); j++) {
			int sum1 = 0, sum2 = 0;
			for (int k = 0; k < Y[pos].size(); k++) {
				int V1 = 0;
				if (X[pos][i] == Y[pos][k]) V1 = 0;
				else if (X[pos][j] == Y[pos][k]) V1 = 1;
				else V1 = 2;

				int V2 = 0;
				if (X[pos][j] == Y[pos][k]) V2 = 0;
				else if (X[pos][i] == Y[pos][k]) V2 = 1;
				else V2 = 2;

				int m1 = 0; for (int l = 0; l <= V1; l++) m1 = max(m1, dp[Y[pos][k].first][l]); sum1 += m1;
				int m2 = 0; for (int l = 0; l <= V2; l++) m2 = max(m2, dp[Y[pos][k].first][l]); sum2 += m2;
			}

			// sum1 を使う場合
			int v1 = 1; if (X[pos][i].first == par[pos]) v1 = 3; if (X[pos][j].first == par[pos]) v1 = 2;
			dp[pos][v1] = max(dp[pos][v1], sum1 + X[pos][i].second + X[pos][j].second);

			int v2 = 1; if (X[pos][j].first == par[pos]) v2 = 3; if (X[pos][i].first == par[pos]) v2 = 2;
			dp[pos][v2] = max(dp[pos][v2], sum2 + X[pos][i].second + X[pos][j].second);
		}
	}
}

int solve_Output() {
	for (int i = 1; i <= N - 1; i++) {
		X[A[i]].push_back(make_pair(B[i], C[i]));
		X[B[i]].push_back(make_pair(A[i], C[i]));
	}
	dfs1(1);
	dfs2(1);
	return max(dp[1][0], dp[1][1]);
}

void random_generate() {
	init();
	N = 7;
	for (int i = 1; i <= N - 1; i++) {
		A[i] = rand() % i + 1; B[i] = i + 1; C[i] = rand() % 3 + 1;
	}
}

int main() {
	cin >> N;
	for (int i = 1; i <= N - 1; i++) cin >> A[i] >> B[i] >> C[i];
	cout << solve_Output() << endl;
	/*for (int i = 1; i <= 10000; i++) {
		random_generate();
		
		int J1 = solve_Jury();
		int J2 = solve_Output();

		if (J1 != J2) {
			cout << "Wrong Answer on Test #" << i << endl;
			cout << "Jury = " << J1 << ", Output = " << J2 << endl;
			cout << endl;
			cout << N << endl;
			for (int j = 1; j <= N - 1; j++) cout << A[j] << " " << B[j] << " " << C[j] << endl;
			cout << endl;
		}
	}*/
	return 0;
}

Compilation message (stderr)

beads.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
beads.cpp: In function 'void solve(int, int, int, int)':
beads.cpp:20:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < X[i].size(); j++) {
                   ~~^~~~~~~~~~~~~
beads.cpp:21:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = j + 1; k < X[i].size(); k++) {
                        ~~^~~~~~~~~~~~~
beads.cpp: In function 'void dfs1(int)':
beads.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
beads.cpp: In function 'void dfs2(int)':
beads.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Y[pos].size(); i++) dfs2(Y[pos][i].first);
                  ~~^~~~~~~~~~~~~~~
beads.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Y[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
beads.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
beads.cpp:69:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i + 1; j < X[pos].size(); j++) {
                       ~~^~~~~~~~~~~~~~~
beads.cpp:71:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < Y[pos].size(); k++) {
                    ~~^~~~~~~~~~~~~~~

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