#654817 (C++14) No.1600 Many Shortest Path Problems

提出ソース

結果

問題	No.1600 Many Shortest Path Problems
ユーザー	e869120
提出日時	2021-05-07 14:36:28
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA (最新) AC (最初)
実行時間	-
コード長	5,127 bytes
コンパイル時間	1,077 ms
コンパイル使用メモリ	84,592 KB
実行使用メモリ	94,976 KB
最終ジャッジ日時	2024-07-01 14:16:44
合計ジャッジ時間	22,754 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	17 ms 22,144 KB
testcase_01	AC	16 ms 22,272 KB
testcase_02	AC	16 ms 22,144 KB
testcase_03	AC	17 ms 22,144 KB
testcase_04	AC	844 ms 94,848 KB
testcase_05	AC	836 ms 94,720 KB
testcase_06	AC	16 ms 22,272 KB
testcase_07	AC	17 ms 22,144 KB
testcase_08	WA	-
testcase_09	AC	17 ms 22,144 KB
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	AC	16 ms 22,016 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	AC	17 ms 22,144 KB
testcase_28	AC	16 ms 22,272 KB
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	AC	17 ms 22,144 KB
testcase_34	AC	17 ms 22,016 KB
testcase_35	AC	571 ms 94,336 KB
testcase_36	AC	415 ms 92,780 KB
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	AC	676 ms 77,952 KB
testcase_46	WA	-
testcase_47	AC	683 ms 74,368 KB
testcase_48	WA	-
testcase_49	AC	17 ms 22,144 KB
testcase_50	AC	17 ms 22,144 KB
testcase_51	AC	16 ms 22,144 KB
testcase_52	AC	17 ms 22,144 KB
testcase_53	AC	16 ms 22,144 KB

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

ソースコード

raw source code

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

class UnionFind {
public:
	vector<int> par;

	void init(int sz) {
		par.resize(sz, -1);
	}
	int root(int pos) {
		if (par[pos] == -1) return pos;
		par[pos] = root(par[pos]);
		return par[pos];
	}
	void unite(int u, int v) {
		u = root(u); v = root(v);
		if (u == v) return;
		par[u] = v;
	}
	bool same(int u, int v) {
		if (root(u) == root(v)) return true;
		return false;
	}
};

class RangeMin {
public:
	int size_ = 1;
	vector<int> dat;

	void init(int sz) {
		while (size_ <= sz) size_ *= 2;
		dat.resize(size_ * 2, (1 << 30));
	}
	void update(int pos, int x) {
		pos += size_;
		dat[pos] = x;
		while (pos >= 2) {
			pos >>= 1;
			dat[pos] = min(dat[pos * 2], dat[pos * 2 + 1]);
		}
	}
	int query_(int l, int r, int a, int b, int u) {
		if (l <= a && b <= r) return dat[u];
		if (r <= a || b <= l) return (1 << 30);
		int v1 = query_(l, r, a, (a + b) >> 1, u * 2);
		int v2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
		return min(v1, v2);
	}
	int query(int l, int r) {
		return query_(l, r, 0, size_, 1);
	}
};

// 入力ほか
long long mod = 1000000007;
long long N, M, Q;
long long A[1 << 18], B[1 << 18], C[1 << 18];
long long X[1 << 18], Y[1 << 18], Z[1 << 18];
bool mst[1 << 18];

// 最小全域木
UnionFind UF;
long long dist1[1 << 18];
long long dist2[1 << 18];
long long ord[1 << 18];
long long cl[1 << 18];
long long cr[1 << 18], cnts;
long long par[1 << 18][24], pre[1 << 18];
vector<pair<int, int>> G[1 << 18], H[1 << 18];
vector<int> I[1 << 18];

// 最小全域木以外の辺
RangeMin P;
int cntw[1 << 18];
int Important[1 << 18];

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

void adds(int pos, int x) {
	cntw[pos] += x;
	if (cntw[pos] == 1) P.update(pos, pos);
	if (cntw[pos] != 1) P.update(pos, (1 << 30));
}

void dfs(int pos, long long dep1, long long dep2) {
	cnts++;
	cl[pos] = cnts;
	ord[cnts] = pos;
	dist1[pos] = dep1;
	dist2[pos] = dep2;
	for (int i = 0; i < G[pos].size(); i++) {
		if (cl[G[pos][i].first] >= 1) continue;
		par[G[pos][i].first][0] = pos;
		pre[G[pos][i].first] = G[pos][i].second;
		H[pos].push_back(G[pos][i]);
		dfs(G[pos][i].first, dep1 + 1, (dep2 + C[G[pos][i].second]) % mod);
	}
	cr[pos] = cnts;
}

void dfs2(int pos) {
	Important[pre[pos]] = P.query(1, M + 1);
	for (int i = 0; i < H[pos].size(); i++) {
		int to = H[pos][i].first;
		for (int j : I[to]) adds(j, -1);
		dfs2(to);
		for (int j : I[to]) adds(j, 1);
	}
}

int prevs(int pos, int x) {
	for (int i = 21; i >= 0; i--) {
		if (x >= (1 << i)) { pos = par[pos][i]; x -= (1 << i); }
	}
	return pos;
}

int lca(int u, int v) {
	if (dist1[u] > dist1[v]) swap(u, v);
	v = prevs(v, dist1[v] - dist1[u]);
	if (u == v) return u;

	for (int i = 21; i >= 0; i--) {
		if (par[u][i] != par[v][i]) {
			u = par[u][i];
			v = par[v][i];
		}
	}
	return par[u][0];
}

long long getdist1(int u, int v) {
	int w = lca(u, v);
	return dist1[u] + dist1[v] - 2 * dist1[w];
}

long long getdist2(int u, int v) {
	int w = lca(u, v);
	return (dist2[u] + dist2[v] - 2LL * dist2[w] + mod * mod) % mod;
}

int main() {
	// Step #1. 入力
	scanf("%lld%lld", &N, &M);
	for (int i = 1; i <= M; i++) scanf("%lld%lld", &A[i], &B[i]);
	scanf("%lld", &Q);
	for (int i = 1; i <= Q; i++) scanf("%lld%lld%lld", &X[i], &Y[i], &Z[i]);
	C[1] = 2LL;
	for (int i = 2; i <= M; i++) C[i] = (2LL * C[i - 1]) % mod;

	// Step #2. 最小全域木を求める
	UF.init(N + 2);
	for (int i = 1; i <= M; i++) {
		if (UF.same(A[i], B[i]) == false) {
			UF.unite(A[i], B[i]);
			mst[i] = true;
			G[A[i]].push_back(make_pair(B[i], i));
			G[B[i]].push_back(make_pair(A[i], i));
		}
	}
	dfs(1, 0, 0);

	// Step #3. LCA を求める
	for (int i = 1; i <= 21; i++) {
		for (int j = 1; j <= N; j++) par[j][i] = par[par[j][i - 1]][i - 1];
	}
	for (int i = 1; i <= M; i++) {
		if (mst[i] == true) continue;
		I[A[i]].push_back(i);
		I[B[i]].push_back(i);
	}

	// Step #4. 重要な辺を求める
	P.init(M + 2);
	for (int i = 0; i < G[1].size(); i++) {
		int to = G[1][i].first;
		for (int j = cl[to]; j <= cr[to]; j++) {
			for (int k : I[ord[j]]) adds(k, 1);
		}
		dfs2(to);
		for (int j = cl[to]; j <= cr[to]; j++) {
			for (int k : I[ord[j]]) adds(k, -1);
		}
	}

	// Step #5. 答えを求める
	for (int i = 1; i <= Q; i++) {
		int d1 = getdist1(X[i], A[Z[i]]) + 1 + getdist1(B[Z[i]], Y[i]);
		int d2 = getdist1(X[i], B[Z[i]]) + 1 + getdist1(A[Z[i]], Y[i]);
		int d3 = getdist1(X[i], Y[i]);
		if (d1 != d3 && d2 != d3) {
			Answer[i] = getdist2(X[i], Y[i]);
			Answer[i] %= mod;
		}
		else if (Important[Z[i]] == (1 << 30)) {
			Answer[i] = -1;
		}
		else {
			int idx = Important[Z[i]];
			int e1 = getdist1(X[i], A[idx]) + 1 + getdist1(B[idx], Y[i]);
			int e2 = getdist1(X[i], B[idx]) + 1 + getdist1(A[idx], Y[i]);
			if (e1 <= e2) {
				Answer[i] = getdist2(X[i], A[idx]) + C[idx] + getdist2(B[idx], Y[i]);
				Answer[i] %= mod;
			}
			else {
				Answer[i] = getdist2(X[i], B[idx]) + C[idx] + getdist2(A[idx], Y[i]);
				Answer[i] %= mod;
			}
		}
	}

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

yukicoder

結果

テストケース

ソースコード