結果

問題 No.1600 Many Shortest Path Problems
ユーザー 👑 ygussanyygussany
提出日時 2021-05-12 10:16:54
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 683 ms / 4,000 ms
コード長 4,783 bytes
コンパイル時間 577 ms
コンパイル使用メモリ 33,956 KB
実行使用メモリ 45,028 KB
最終ジャッジ日時 2023-09-14 06:57:24
合計ジャッジ時間 18,948 ms
ジャッジサーバーID
(参考情報)
judge14 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
19,824 KB
testcase_01 AC 8 ms
19,844 KB
testcase_02 AC 7 ms
19,892 KB
testcase_03 AC 7 ms
19,780 KB
testcase_04 AC 569 ms
40,172 KB
testcase_05 AC 530 ms
41,724 KB
testcase_06 AC 6 ms
19,896 KB
testcase_07 AC 7 ms
19,888 KB
testcase_08 AC 7 ms
19,844 KB
testcase_09 AC 7 ms
19,892 KB
testcase_10 AC 140 ms
22,964 KB
testcase_11 AC 192 ms
23,736 KB
testcase_12 AC 370 ms
28,120 KB
testcase_13 AC 486 ms
35,060 KB
testcase_14 AC 543 ms
41,536 KB
testcase_15 AC 8 ms
19,896 KB
testcase_16 AC 8 ms
19,932 KB
testcase_17 AC 406 ms
31,212 KB
testcase_18 AC 519 ms
39,752 KB
testcase_19 AC 8 ms
19,836 KB
testcase_20 AC 8 ms
19,724 KB
testcase_21 AC 421 ms
31,508 KB
testcase_22 AC 7 ms
19,920 KB
testcase_23 AC 7 ms
19,852 KB
testcase_24 AC 533 ms
40,164 KB
testcase_25 AC 7 ms
19,788 KB
testcase_26 AC 8 ms
19,832 KB
testcase_27 AC 8 ms
19,848 KB
testcase_28 AC 8 ms
19,896 KB
testcase_29 AC 683 ms
34,268 KB
testcase_30 AC 640 ms
33,964 KB
testcase_31 AC 429 ms
31,320 KB
testcase_32 AC 282 ms
30,084 KB
testcase_33 AC 7 ms
19,840 KB
testcase_34 AC 6 ms
19,888 KB
testcase_35 AC 240 ms
36,792 KB
testcase_36 AC 146 ms
33,924 KB
testcase_37 AC 7 ms
19,888 KB
testcase_38 AC 615 ms
34,048 KB
testcase_39 AC 7 ms
19,900 KB
testcase_40 AC 661 ms
33,948 KB
testcase_41 AC 267 ms
34,268 KB
testcase_42 AC 275 ms
33,964 KB
testcase_43 AC 275 ms
34,008 KB
testcase_44 AC 285 ms
33,744 KB
testcase_45 AC 646 ms
34,256 KB
testcase_46 AC 542 ms
44,676 KB
testcase_47 AC 649 ms
45,028 KB
testcase_48 AC 553 ms
44,316 KB
testcase_49 AC 6 ms
26,292 KB
testcase_50 AC 7 ms
28,452 KB
testcase_51 AC 7 ms
28,388 KB
testcase_52 AC 7 ms
28,500 KB
testcase_53 AC 7 ms
28,412 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <stdio.h>
#include <stdlib.h>

const int Mod = 1000000007;

typedef struct List {
	struct List *next;
	int v, id;
} list;

typedef struct {
	int *par, *size;
} UF_forest;

void UF_initialize(UF_forest *F, int n)
{
	int i;
	F->par = (int*)malloc(sizeof(int) * (n + 1));
	F->size = (int*)malloc(sizeof(int) * (n + 1));
	for (i = 1; i <= n; i++) {
		F->par[i] = i;
		F->size[i] = 1;
	}
}

int UF_root(UF_forest *F, int v)
{
	if (F->par[v] == v) return v;
	else {
		F->par[v] = UF_root(F, F->par[v]);
		return F->par[v];
	}
}

void UF_merge(UF_forest *F, int u, int v)
{
	u = UF_root(F, u);
	v = UF_root(F, v);
	if (u == v) return;
	else if (F->size[u] > F->size[v]) {
		F->par[v] = u;
		F->size[u] += F->size[v];
	} else {
		F->par[u] = v;
		F->size[v] += F->size[u];
	}
}

int LCA(int par[][200001], int depth[], int u, int w)
{
	int i;
	while (depth[u] > depth[w]) {
		for (i = 0; depth[par[i][u]] >= depth[w]; i++);
		u = par[i-1][u];
	}
	while (depth[u] < depth[w]) {
		for (i = 0; depth[par[i][w]] >= depth[u]; i++);
		w = par[i-1][w];
	}
	while (u != w) {
		for (i = 0; par[i][u] != par[i][w]; i++);
		if (i > 0) i--;
		u = par[i][u];
		w = par[i][w];
	}
	return u;
}

int distance(int par[][200001], int dist[][200001], int depth[], int u, int w)
{
	int i;
	long long ans = 0;
	while (depth[u] > depth[w]) {
		for (i = 0; depth[par[i][u]] >= depth[w]; i++);
		ans += dist[i-1][u];
		u = par[i-1][u];
	}
	while (depth[u] < depth[w]) {
		for (i = 0; depth[par[i][w]] >= depth[u]; i++);
		ans += dist[i-1][w];
		w = par[i-1][w];
	}
	while (u != w) {
		for (i = 0; par[i][u] != par[i][w]; i++);
		if (i > 0) i--;
		ans += dist[i][u] + dist[i][w];
		u = par[i][u];
		w = par[i][w];
	}
	return (int)(ans % Mod);
}

int main()
{
	int i, N, M, A[200001], B[200001];
	scanf("%d %d", &N, &M);
	for (i = 0; i < M; i++) scanf("%d %d", &(A[i]), &(B[i]));
	
	int pow[200001];
	for (i = 1, pow[0] = 2; i < M; i++) pow[i] = pow[i-1] * 2 % Mod;
	
	int j, u, w, tree[200001] = {};
	list *adj[200001] = {}, e[400001], *p;
	UF_forest F;
	UF_initialize(&F, N);
	for (i = 0, j = 0; i < M; i++) {
		u = UF_root(&F, A[i]);
		w = UF_root(&F, B[i]);
		if (u != w) {
			UF_merge(&F, u, w);
			tree[i] = 1;
			u = A[i];
			w = B[i];
			e[j].v = w;
			e[j].id = i;
			e[j].next = adj[u];
			adj[u] = &(e[j++]);
			e[j].v = u;
			e[j].id = i;
			e[j].next = adj[w];
			adj[w] = &(e[j++]);
		}
	}
	
	int x, par[20][200001] = {}, par_edge[200001], dist[20][200001], depth[200001], q[200001], head, tail;
	par[0][1] = -1;
	par_edge[1] = -1;
	depth[1] = 0;
	depth[0] = -1;
	q[0] = 1;
	for (head = 0, tail = 1; head < tail; head++) {
		u = q[head];
		for (p = adj[u]; p != NULL; p = p->next) {
			w = p->v;
			if (par[0][w] != 0) continue;
			par[0][w] = u;
			par_edge[w] = p->id;
			dist[0][w] = pow[p->id];
			for (i = 0, x = u; par[i][x] > 0; x = par[i++][x]) {
				par[i+1][w] = par[i][x];
				dist[i+1][w] = dist[i][w] + dist[i][x];
				if (dist[i+1][w] >= Mod) dist[i+1][w] -= Mod;
			}
			depth[w] = depth[u] + 1;
			q[tail++] = w;
		}
	}
	
	int alt[200001];
	for (i = 0; i < M; i++) alt[i] = -1;
	for (i = 0; i < M; i++) {
		if (tree[i] != 0) continue;
		x = LCA(par, depth, A[i], B[i]);
		
		u = A[i];
		while (depth[u] > depth[x]) {
			j = par_edge[u];
			if (j < 0) break;
			w = (depth[A[j]] < depth[B[j]])? A[j]: B[j];
			if (depth[w] < depth[x]) break;
			
			if (alt[j] == -1) alt[j] = i;
			par_edge[u] = par_edge[x];
			u = w;
		}
	
		u = B[i];
		while (depth[u] > depth[x]) {
			j = par_edge[u];
			if (j < 0) break;
			w = (depth[A[j]] < depth[B[j]])? A[j]: B[j];
			if (depth[w] < depth[x]) break;
			
			if (alt[j] == -1) alt[j] = i;
			par_edge[u] = par_edge[x];
			u = w;
		}
	}
	
	int Q, y, z, lca[5];
	scanf("%d", &Q);
	for (i = 1; i <= Q; i++) {
		scanf("%d %d %d", &x, &y, &z);
		z--;
		if (tree[z] == 0) {
			printf("%d\n", distance(par, dist, depth, x, y));
			continue;
		}
		
		u = (depth[A[z]] < depth[B[z]])? A[z]: B[z];
		w = A[z] + B[z] - u;
		lca[0] = LCA(par, depth, x, y);
		lca[1] = LCA(par, depth, x, w);
		lca[2] = LCA(par, depth, y, u);
		lca[3] = LCA(par, depth, y, w);
		lca[4] = LCA(par, depth, x, u);
		if (depth[u] >= depth[lca[0]] && ((lca[1] == w && lca[2] == lca[0]) || (lca[3] == w && lca[4] == lca[0]))) {
			if (alt[z] == -1) printf("-1\n");
			else {
				if (LCA(par, depth, LCA(par, depth, x, A[alt[z]]), w) == w || LCA(par, depth, LCA(par, depth, y, B[alt[z]]), w) == w) printf("%lld\n", ((long long)pow[alt[z]] + distance(par, dist, depth, x, A[alt[z]]) + distance(par, dist, depth, y, B[alt[z]])) % Mod);
				else printf("%lld\n", ((long long)pow[alt[z]] + distance(par, dist, depth, x, B[alt[z]]) + distance(par, dist, depth, y, A[alt[z]])) % Mod);
			}
		} else printf("%d\n", distance(par, dist, depth, x, y));
	}
	fflush(stdout);
	return 0;
}
0