結果

問題 No.1212 Second Path
ユーザー e869120e869120
提出日時 2021-02-26 10:26:57
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 693 ms / 3,000 ms
コード長 4,346 bytes
コンパイル時間 1,513 ms
コンパイル使用メモリ 94,488 KB
実行使用メモリ 41,544 KB
最終ジャッジ日時 2024-10-02 00:08:09
合計ジャッジ時間 18,139 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 182 ms
39,432 KB
testcase_01 AC 591 ms
41,420 KB
testcase_02 AC 596 ms
41,416 KB
testcase_03 AC 602 ms
41,544 KB
testcase_04 AC 693 ms
41,416 KB
testcase_05 AC 592 ms
41,164 KB
testcase_06 AC 169 ms
40,876 KB
testcase_07 AC 414 ms
36,992 KB
testcase_08 AC 374 ms
36,356 KB
testcase_09 AC 356 ms
36,348 KB
testcase_10 AC 397 ms
37,244 KB
testcase_11 AC 379 ms
36,476 KB
testcase_12 AC 402 ms
37,156 KB
testcase_13 AC 391 ms
37,240 KB
testcase_14 AC 385 ms
36,988 KB
testcase_15 AC 388 ms
36,760 KB
testcase_16 AC 369 ms
36,868 KB
testcase_17 AC 186 ms
39,372 KB
testcase_18 AC 43 ms
19,336 KB
testcase_19 AC 43 ms
19,068 KB
testcase_20 AC 44 ms
18,948 KB
testcase_21 AC 42 ms
19,076 KB
testcase_22 AC 43 ms
19,072 KB
testcase_23 AC 37 ms
18,944 KB
testcase_24 AC 40 ms
18,948 KB
testcase_25 AC 40 ms
19,020 KB
testcase_26 AC 39 ms
19,080 KB
testcase_27 AC 41 ms
18,952 KB
testcase_28 AC 41 ms
18,948 KB
testcase_29 AC 354 ms
41,424 KB
testcase_30 AC 357 ms
41,288 KB
testcase_31 AC 352 ms
41,292 KB
testcase_32 AC 257 ms
32,088 KB
testcase_33 AC 204 ms
29,320 KB
testcase_34 AC 338 ms
35,884 KB
testcase_35 AC 65 ms
20,800 KB
testcase_36 AC 273 ms
32,640 KB
testcase_37 AC 256 ms
31,704 KB
testcase_38 AC 279 ms
32,188 KB
testcase_39 AC 155 ms
26,396 KB
testcase_40 AC 43 ms
19,244 KB
testcase_41 AC 269 ms
31,980 KB
testcase_42 AC 12 ms
16,000 KB
testcase_43 AC 11 ms
16,128 KB
testcase_44 AC 11 ms
16,128 KB
testcase_45 AC 176 ms
41,004 KB
testcase_46 AC 177 ms
41,128 KB
testcase_47 AC 174 ms
41,004 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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(F[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 Rand() {
	int s = 0, t = 1;
	for (int i = 0; i < 30; i++) {
		if (rand() % 2 == 0) s += t;
		t *= 2;
	}
	return s;
}

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