Submission #48046

#	Time	Username	Problem	Language	Result	Execution time	Memory
48046		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[209], B[209], C[209], par[209], d[209][209]; vector<pair<int, int>>Z[209], X[209]; bool used[209];
int dp[209][4][2], maxn; vector<int>S;

void dfs(int pos, int pars) {
	used[pos] = true; par[pos] = pars;
	for (int i = 0; i < Z[pos].size(); i++) {
		if (used[Z[pos][i].first] == true) continue;
		X[pos].push_back(Z[pos][i]);
		dfs(Z[pos][i].first, pos);
	}
	S.push_back(pos);
}

int main() {
	cin >> N;
	for (int i = 1; i <= N - 1; i++) {
		cin >> A[i] >> B[i] >> C[i]; d[A[i]][B[i]] = C[i]; d[B[i]][A[i]] = C[i];
		Z[A[i]].push_back(make_pair(B[i], C[i]));
		Z[B[i]].push_back(make_pair(A[i], C[i]));
	}
	dfs(1, -1);
	for (int i = 0; i <= N; i++) { for (int j = 0; j <= 4; j++) { dp[i][j][0] = -(1 << 30); dp[i][j][1] = -(1 << 30); } }

	for (int i = 0; i < S.size(); i++) {
		int pos = S[i];

		// 次数 = 0 - 次数 = 1, 上を使う
		int s = 0;
		for (int j = 0; j < X[pos].size(); j++) {
			int maxn = -1;
			for (int k = 0; k <= 2; k++) maxn = max(maxn, dp[X[pos][j].first][k][0]);
			if (maxn == -1 || s == -(1 << 30)) s = -(1 << 30);
			else s += maxn;
		}
		dp[pos][0][1] = s;
		dp[pos][1][0] = s;
		
		// 次数 = 1, 上を使わない - 次数 = 2, 上を使う
		for (int a1 = 0; a1 < X[pos].size(); a1++) {
			int sum = 0;
			for (int j = 0; j < X[pos].size(); j++) {
				int maxn = -1, bit = 0; if (a1 == j) bit = 1;
				for (int k = 0; k <= 2; k++) maxn = max(maxn, dp[X[pos][j].first][k][bit]);
				if (maxn == -1 || sum == -(1 << 30)) sum = -(1 << 30);
				else sum += maxn;
			}
			dp[pos][1][1] = max(dp[pos][1][1], sum);
			if (pos != 1) dp[pos][2][0] = max(dp[pos][2][0], sum + d[par[pos]][pos] + d[X[pos][a1].first][pos]);
		}

		// 次数 = 2, 上を使わない
		for (int a1 = 0; a1 < X[pos].size(); a1++) {
			for (int a2 = 0; a2 < X[pos].size(); a2++) {
				if (a1 == a2) continue;

				int sum = 0;
				for (int j = 0; j < X[pos].size(); j++) {
					int maxn = -1, bit = 0; if (a1 == j || a2 == j) bit = 1;
					for (int k = 0; k <= 2; k++) maxn = max(maxn, dp[X[pos][j].first][k][bit]);
					if (maxn == -1 || sum == -(1 << 30)) sum = -(1 << 30);
					else sum += maxn;
				}
				dp[pos][2][1] = max(dp[pos][2][1], sum + d[X[pos][a1].first][pos] + d[X[pos][a2].first][pos]);
			}
		}
	}
	int ret = -(1 << 30);
	for (int i = 0; i <= 2; i++) ret = max(ret, dp[1][i][1]);
	cout << ret << endl;
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:11:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Z[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) {
                  ~~^~~~~~~~~~
beads.cpp:34:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < X[pos].size(); j++) {
                   ~~^~~~~~~~~~~~~~~
beads.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int a1 = 0; a1 < X[pos].size(); a1++) {
                    ~~~^~~~~~~~~~~~~~~
beads.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < X[pos].size(); j++) {
                    ~~^~~~~~~~~~~~~~~
beads.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int a1 = 0; a1 < X[pos].size(); a1++) {
                    ~~~^~~~~~~~~~~~~~~
beads.cpp:58:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int a2 = 0; a2 < X[pos].size(); a2++) {
                     ~~~^~~~~~~~~~~~~~~
beads.cpp:62:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < X[pos].size(); j++) {
                     ~~^~~~~~~~~~~~~~~
beads.cpp:27:76: warning: iteration 4 invokes undefined behavior [-Waggressive-loop-optimizations]
  for (int i = 0; i <= N; i++) { for (int j = 0; j <= 4; j++) { dp[i][j][0] = -(1 << 30); dp[i][j][1] = -(1 << 30); } }
                                                                ~~~~~~~~~~~~^~~~~~~~~~~~
beads.cpp:27:51: note: within this loop
  for (int i = 0; i <= N; i++) { for (int j = 0; j <= 4; j++) { dp[i][j][0] = -(1 << 30); dp[i][j][1] = -(1 << 30); } }
                                                 ~~^~~~

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