Submission #104516

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

beads

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

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

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);
	}
}

int dp[100009][4];

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][j].first == par[pos]) v1 = 3; if (X[pos][i].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][i].first == par[pos]) v2 = 3; if (X[pos][j].first == par[pos]) v2 = 2;
			dp[pos][v2] = max(dp[pos][v2], sum2 + X[pos][i].second + X[pos][j].second);
		}
	}
}

int N, A[100009], B[100009], C[100009];

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N - 1; i++) {
		scanf("%d%d%d", &A[i], &B[i], &C[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);
	cout << max(dp[1][0], dp[1][1]) << 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 dfs1(int)':
beads.cpp:12: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:24: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:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Y[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
beads.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
beads.cpp:33:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i + 1; j < X[pos].size(); j++) {
                       ~~^~~~~~~~~~~~~~~
beads.cpp:35:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < Y[pos].size(); k++) {
                    ~~^~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
beads.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &A[i], &B[i], &C[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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