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

提出ソース

結果

問題	No.1600 Many Shortest Path Problems
ユーザー	e869120
提出日時	2021-05-07 15:39:48
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	806 ms / 4,000 ms
コード長	5,774 bytes
コンパイル時間	1,515 ms
コンパイル使用メモリ	98,792 KB
実行使用メモリ	108,008 KB
最終ジャッジ日時	2023-09-14 06:52:00
合計ジャッジ時間	23,716 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	13 ms 46,644 KB
testcase_01	AC	13 ms 46,676 KB
testcase_02	AC	13 ms 46,840 KB
testcase_03	AC	13 ms 46,712 KB
testcase_04	AC	806 ms 107,652 KB
testcase_05	AC	779 ms 107,868 KB
testcase_06	AC	13 ms 46,556 KB
testcase_07	AC	13 ms 46,492 KB
testcase_08	AC	13 ms 46,568 KB
testcase_09	AC	13 ms 46,576 KB
testcase_10	AC	287 ms 56,948 KB
testcase_11	AC	356 ms 59,244 KB
testcase_12	AC	519 ms 73,848 KB
testcase_13	AC	658 ms 96,348 KB
testcase_14	AC	719 ms 107,432 KB
testcase_15	AC	13 ms 46,488 KB
testcase_16	AC	13 ms 46,592 KB
testcase_17	AC	561 ms 83,984 KB
testcase_18	AC	723 ms 107,524 KB
testcase_19	AC	12 ms 46,704 KB
testcase_20	AC	12 ms 46,704 KB
testcase_21	AC	566 ms 83,580 KB
testcase_22	AC	13 ms 46,520 KB
testcase_23	AC	13 ms 46,592 KB
testcase_24	AC	721 ms 107,436 KB
testcase_25	AC	13 ms 46,552 KB
testcase_26	AC	13 ms 46,700 KB
testcase_27	AC	13 ms 46,564 KB
testcase_28	AC	13 ms 46,540 KB
testcase_29	AC	685 ms 91,796 KB
testcase_30	AC	630 ms 88,972 KB
testcase_31	AC	548 ms 83,684 KB
testcase_32	AC	552 ms 83,956 KB
testcase_33	AC	13 ms 46,592 KB
testcase_34	AC	13 ms 46,568 KB
testcase_35	AC	561 ms 107,488 KB
testcase_36	AC	377 ms 108,008 KB
testcase_37	AC	13 ms 46,496 KB
testcase_38	AC	604 ms 90,540 KB
testcase_39	AC	13 ms 46,716 KB
testcase_40	AC	672 ms 89,324 KB
testcase_41	AC	436 ms 91,876 KB
testcase_42	AC	445 ms 88,856 KB
testcase_43	AC	406 ms 88,712 KB
testcase_44	AC	441 ms 87,324 KB
testcase_45	AC	617 ms 91,632 KB
testcase_46	AC	535 ms 88,888 KB
testcase_47	AC	645 ms 88,772 KB
testcase_48	AC	616 ms 88,296 KB
testcase_49	AC	13 ms 46,636 KB
testcase_50	AC	13 ms 46,568 KB
testcase_51	AC	13 ms 46,512 KB
testcase_52	AC	13 ms 46,764 KB
testcase_53	AC	13 ms 46,624 KB

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

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <tuple>
#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 P1, P2;
vector<tuple<int, int, int>> tup1, tup2;
int Important[1 << 18];

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

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

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. 重要な辺を求める
	P1.init(N + 2);
	P2.init(N + 2);
	for (int i = 1; i <= M; i++) {
		if (mst[i] == true) {
			int idx = A[i]; if (dist1[A[i]] < dist1[B[i]]) idx = B[i];
			tup1.push_back(make_tuple(cl[idx], -i, cr[idx]));
			tup2.push_back(make_tuple(cr[idx], i, cl[idx]));
		}
		if (mst[i] == false) {
			int dl = cl[A[i]], dr = cl[B[i]]; if (dl > dr) swap(dl, dr);
			tup1.push_back(make_tuple(dl, i, dr));
			tup2.push_back(make_tuple(dr, -i, dl));
		}
	}
	sort(tup1.begin(), tup1.end());
	sort(tup2.begin(), tup2.end());
	reverse(tup2.begin(), tup2.end());
	for (int i = 1; i <= M; i++) Important[i] = (1 << 30);

	for (int i = 0; i < tup1.size(); i++) {
		int p1 = get<0>(tup1[i]), p2 = get<2>(tup1[i]), idx = get<1>(tup1[i]);
		if (idx < 0) {
			int ret = P1.query(p1, p2 + 1);
			Important[-idx] = min(Important[-idx], ret);
		}
		else {
			int rem = P1.dat[p2 + P1.size_];
			P1.update(p2, min(rem, idx));
		}
	}
	for (int i = 0; i < tup2.size(); i++) {
		int p1 = get<0>(tup2[i]), p2 = get<2>(tup2[i]), idx = get<1>(tup2[i]);
		if (idx >= 0) {
			int ret = P2.query(p2, p1 + 1);
			Important[idx] = min(Important[idx], ret);
		}
		else {
			int rem = P2.dat[p2 + P2.size_];
			P2.update(p2, min(rem, -idx));
		}
	}

	// 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) || mst[Z[i]] == false) {
			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

結果

テストケース

ソースコード