結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 143 ms
51,176 KB
testcase_01 AC 436 ms
52,964 KB
testcase_02 AC 464 ms
52,740 KB
testcase_03 AC 447 ms
54,552 KB
testcase_04 AC 441 ms
52,596 KB
testcase_05 AC 444 ms
52,500 KB
testcase_06 AC 134 ms
53,608 KB
testcase_07 AC 315 ms
48,792 KB
testcase_08 AC 290 ms
48,456 KB
testcase_09 AC 339 ms
47,876 KB
testcase_10 AC 311 ms
49,368 KB
testcase_11 AC 292 ms
47,988 KB
testcase_12 AC 309 ms
50,088 KB
testcase_13 AC 304 ms
49,244 KB
testcase_14 AC 303 ms
48,644 KB
testcase_15 AC 313 ms
48,280 KB
testcase_16 AC 295 ms
48,308 KB
testcase_17 AC 143 ms
50,820 KB
testcase_18 AC 38 ms
35,164 KB
testcase_19 AC 38 ms
35,164 KB
testcase_20 AC 38 ms
35,036 KB
testcase_21 AC 39 ms
35,168 KB
testcase_22 AC 38 ms
35,164 KB
testcase_23 AC 33 ms
35,040 KB
testcase_24 AC 35 ms
35,040 KB
testcase_25 AC 36 ms
34,908 KB
testcase_26 AC 35 ms
35,036 KB
testcase_27 AC 37 ms
35,032 KB
testcase_28 AC 36 ms
35,036 KB
testcase_29 AC 262 ms
52,764 KB
testcase_30 AC 260 ms
52,868 KB
testcase_31 AC 284 ms
52,784 KB
testcase_32 AC 219 ms
44,856 KB
testcase_33 AC 176 ms
44,584 KB
testcase_34 AC 277 ms
47,476 KB
testcase_35 AC 59 ms
36,280 KB
testcase_36 AC 222 ms
45,036 KB
testcase_37 AC 209 ms
44,392 KB
testcase_38 AC 229 ms
44,892 KB
testcase_39 AC 141 ms
42,412 KB
testcase_40 AC 41 ms
35,196 KB
testcase_41 AC 215 ms
46,252 KB
testcase_42 AC 9 ms
36,556 KB
testcase_43 AC 9 ms
34,512 KB
testcase_44 AC 9 ms
34,764 KB
testcase_45 AC 134 ms
53,192 KB
testcase_46 AC 141 ms
53,500 KB
testcase_47 AC 140 ms
52,036 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