#622433 (C++14) No.1212 Second Path

提出ソース

結果

問題	No.1212 Second Path
ユーザー	e869120
提出日時	2021-02-26 10:11:53
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	4,224 bytes
コンパイル時間	1,305 ms
コンパイル使用メモリ	94,012 KB
実行使用メモリ	448,740 KB
最終ジャッジ日時	2024-04-09 23:17:59
合計ジャッジ時間	40,143 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	178 ms 58,404 KB
testcase_01	AC	624 ms 54,652 KB
testcase_02	AC	627 ms 56,504 KB
testcase_03	AC	627 ms 55,376 KB
testcase_04	AC	600 ms 54,456 KB
testcase_05	AC	629 ms 56,720 KB
testcase_06	AC	159 ms 52,240 KB
testcase_07	AC	2,990 ms 67,780 KB
testcase_08	AC	2,227 ms 62,620 KB
testcase_09	AC	2,736 ms 74,712 KB
testcase_10	AC	2,794 ms 64,516 KB
testcase_11	AC	2,210 ms 60,944 KB
testcase_12	AC	2,898 ms 63,268 KB
testcase_13	AC	2,148 ms 59,380 KB
testcase_14	AC	2,316 ms 58,788 KB
testcase_15	AC	2,098 ms 57,768 KB
testcase_16	AC	2,405 ms 61,332 KB
testcase_17	AC	178 ms 50,900 KB
testcase_18	AC	43 ms 35,296 KB
testcase_19	AC	42 ms 35,292 KB
testcase_20	AC	43 ms 37,080 KB
testcase_21	AC	42 ms 37,212 KB
testcase_22	AC	41 ms 35,168 KB
testcase_23	AC	36 ms 36,960 KB
testcase_24	AC	38 ms 34,912 KB
testcase_25	AC	38 ms 35,040 KB
testcase_26	AC	38 ms 37,084 KB
testcase_27	AC	38 ms 35,168 KB
testcase_28	AC	38 ms 35,164 KB
testcase_29	TLE	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

// 入力
long long N, A[1 << 18], B[1 << 18], C[1 << 18];
long long Q, X[1 << 18], Y[1 << 18];

// 出力
long long Answer[1 << 18];

// グラフ
vector<pair<int, int>> G[1 << 18];
vector<pair<long long, int>> H[1 << 18];
vector<int> I;
int dp[1 << 18];
int col[1 << 18];
int representative[1 << 18];
long long par[1 << 18];
long long dist[1 << 18];
long long dist2[1 << 18];

void dfs1(int pos) {
	dp[pos] = 1;
	for (int i = 0; i < G[pos].size(); i++) {
		if (dp[G[pos][i].first] >= 1) continue;
		dfs1(G[pos][i].first);
		dp[pos] += dp[G[pos][i].first];
	}
}

void dfs2(int pos, int pre, int cols, long long dep, long long dep2) {
	col[pos] = cols;
	dist[pos] = dep;
	dist2[pos] = dep2;
	par[pos] = pre;
	for (int i = 0; i < G[pos].size(); i++) {
		if (G[pos][i].first == pre) continue;
		long long new_dep2 = dep2;
		for (int j = 0; j < H[pos].size(); j++) {
			if (H[pos][j].second == pre) continue;
			if (H[pos][j].second == G[pos][i].first) continue;
			new_dep2 = min(new_dep2, H[pos][j].first);
			break;
		}
		dfs2(G[pos][i].first, pos, cols, dep + C[G[pos][i].second], new_dep2);
		I.push_back(G[pos][i].second);
	}
}

void solve(vector<int> E, vector<int> D) {
	if (D.size() == 0) return;

	// Step A: 前処理
	vector<int> F;
	for (int i : E) {
		F.push_back(A[i]);
		F.push_back(B[i]);
		G[A[i]].push_back(make_pair(B[i], i));
		G[B[i]].push_back(make_pair(A[i], i));
	}
	sort(F.begin(), F.end());
	F.erase(unique(F.begin(), F.end()), F.end());

	// Step B. 重心を見つける
	dfs1(E[0]);
	int grav = -1, minx = (1 << 30);
	for (int i : F) {
		int rem = F.size() - 1, maxv = 0;
		for (int j = 0; j < G[i].size(); j++) {
			int to = G[i][j].first;
			if (dp[to] > dp[i]) continue;
			maxv = max(maxv, dp[to]);
			rem -= dp[to];
		}
		maxv = max(maxv, rem);
		if (minx > maxv) {
			minx = maxv;
			grav = i;
		}
	}

	// Step C: 深さ優先探索
	int cnts = 0;
	vector<vector<int>> J;
	dist[grav] = 0;
	dist2[grav] = (1LL << 60);
	for (int i = 0; i < G[grav].size(); i++) {
		cnts++;
		int to = G[grav][i].first;
		int idx = G[grav][i].second;
		representative[cnts] = to;
		I.clear();
		dfs2(to, grav, cnts, C[idx], 1LL << 60);
		J.push_back(I);
	}

	// Step D: クエリに答える
	vector<vector<int>> K(cnts, vector<int>(0, 0));
	for (int idx : D) {
		if (col[X[idx]] == col[Y[idx]]) {
			K[col[X[idx]] - 1].push_back(idx);
			continue;
		}
		long long d1 = dist[X[idx]] + dist[Y[idx]];
		long long d2 = dist2[X[idx]];
		long long d3 = dist2[Y[idx]];
		long long d4 = (1LL << 60), d5 = (1LL << 60), d6 = (1LL << 60);
		if (X[idx] != grav) {
			for (int i = 0; i < H[X[idx]].size(); i++) {
				if (H[X[idx]][i].second == par[X[idx]]) continue;
				d4 = H[X[idx]][i].first;
				break;
			}
		}
		if (Y[idx] != grav) {
			for (int i = 0; i < H[Y[idx]].size(); i++) {
				if (H[Y[idx]][i].second == par[Y[idx]]) continue;
				d5 = H[Y[idx]][i].first;
				break;
			}
		}
		for (int i = 0; i < H[grav].size(); i++) {
			if (H[grav][i].second == representative[col[X[idx]]]) continue;
			if (H[grav][i].second == representative[col[Y[idx]]]) continue;
			d6 = H[grav][i].first;
			break;
		}
		Answer[idx] = d1 + 2LL * min({ d2, d3, d4, d5, d6 });
		if (Answer[idx] >= (1LL << 60)) Answer[idx] = -1;
	}

	// Step E: 初期化
	for (int i : F) {
		dp[i] = 0; col[i] = 0;
		dist[i] = 0; dist2[i] = 0; par[i] = 0;
		G[i].clear();
	}
	for (int i = 1; i <= cnts; i++) representative[i] = 0;

	// Step F: 木の分解
	for (int i = 0; i < cnts; i++) {
		solve(J[i], K[i]);
	}
}

int main() {
	// Step #1. 入力
	scanf("%lld", &N);
	for (int i = 1; i <= N - 1; i++) {
		scanf("%lld%lld%lld", &A[i], &B[i], &C[i]);
		H[A[i]].push_back(make_pair(C[i], B[i]));
		H[B[i]].push_back(make_pair(C[i], A[i]));
	}
	scanf("%lld", &Q);
	for (int i = 1; i <= Q; i++) scanf("%lld%lld", &X[i], &Y[i]);
	for (int i = 1; i <= N; i++) sort(H[i].begin(), H[i].end());

	// Step #2. 重心分解
	vector<int> E, D;
	for (int i = 1; i <= N - 1; i++) E.push_back(i);
	for (int i = 1; i <= Q; i++) D.push_back(i);
	solve(E, D);

	// Step #3. 出力
	for (int i = 1; i <= Q; i++) printf("%lld\n", Answer[i]);
	return 0;
}

yukicoder

結果

テストケース

ソースコード