結果

問題 No.1212 Second Path
コンテスト
ユーザー e869120
提出日時 2021-02-26 10:11:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,224 bytes
コンパイル時間 1,211 ms
コンパイル使用メモリ 94,976 KB
実行使用メモリ 511,188 KB
最終ジャッジ日時 2024-10-01 23:56:27
合計ジャッジ時間 39,101 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 29 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

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