Submission #104519

#	Time	Username	Problem	Language	Result	Execution time	Memory
104519		E869120	Beads and wires (APIO14_beads)	C++14	13 / 100	7 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[16];
	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][8];
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 < 8; 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++) {
		int max1 = 0; for (int j = 0; j < 4; j++) max1 = max(max1, dp[Y[pos][i].first][j]); dp[pos][0] += max1;
		int max2 = 0; for (int j = 0; j < 8; j++) max2 = max(max2, dp[Y[pos][i].first][j]); dp[pos][4] += max2;
	}

	// pos を中心に結ぶ場合
	for (int i = 0; i < X[pos].size(); i++) {
		for (int j = i + 1; j < X[pos].size(); j++) {
			// ---------------------- 0 の場合 --------------------------
			if (X[pos][i].first == par[pos] || X[pos][j].first == par[pos]) {
				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;
				}

				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);
			}
			
			// ---------------------- 4 の場合 --------------------------
			if (true) {
				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]); if (X[pos][i].first == par[pos] || X[pos][j].first == par[pos]) m1 = max(m1, dp[Y[pos][k].first][l + 4]); } sum1 += m1;
					int m2 = 0; for (int l = 0; l <= V2; l++) { m2 = max(m2, dp[Y[pos][k].first][l]); if (X[pos][i].first == par[pos] || X[pos][j].first == par[pos]) m2 = max(m2, dp[Y[pos][k].first][l + 4]); } sum2 += m2;
				}

				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], dp[1][2], dp[1][3], dp[1][4], dp[1][5], dp[1][6], dp[1][7] });
}

void random_generate() {
	init();
	N = 16;
	for (int i = 1; i <= N - 1; i++) {
		A[i] = rand() % i + 1; B[i] = i + 1; C[i] = rand() % 10000 + 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 <= 1000000; 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:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
beads.cpp:70:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i + 1; j < X[pos].size(); j++) {
                       ~~^~~~~~~~~~~~~~~
beads.cpp:74:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int k = 0; k < Y[pos].size(); k++) {
                     ~~^~~~~~~~~~~~~~~
beads.cpp:99:23: 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