#656265 (C) No.1600 Many Shortest Path Problems

提出ソース

結果

問題	No.1600 Many Shortest Path Problems
ユーザー	👑 ygussany
提出日時	2021-05-12 10:16:54
言語	C (gcc 11.2.0)
結果	AC
実行時間	674 ms / 4,000 ms
コード長	4,783 bytes
コンパイル時間	390 ms
使用メモリ	40,244 KB
最終ジャッジ日時	2023-02-01 21:05:41
合計ジャッジ時間	18,025 ms
ジャッジサーバーID （参考情報）	judge14 / judge13

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間使用メモリ
testcase_00	AC	14 ms 19,956 KB
testcase_01	AC	14 ms 19,868 KB
testcase_02	AC	14 ms 19,872 KB
testcase_03	AC	13 ms 19,824 KB
testcase_04	AC	557 ms 40,152 KB
testcase_05	AC	536 ms 40,196 KB
testcase_06	AC	13 ms 19,820 KB
testcase_07	AC	14 ms 19,956 KB
testcase_08	AC	13 ms 19,892 KB
testcase_09	AC	13 ms 19,828 KB
testcase_10	AC	138 ms 23,036 KB
testcase_11	AC	193 ms 23,792 KB
testcase_12	AC	357 ms 28,132 KB
testcase_13	AC	463 ms 35,028 KB
testcase_14	AC	523 ms 40,096 KB
testcase_15	AC	13 ms 19,872 KB
testcase_16	AC	13 ms 19,876 KB
testcase_17	AC	385 ms 31,308 KB
testcase_18	AC	523 ms 39,724 KB
testcase_19	AC	13 ms 19,896 KB
testcase_20	AC	13 ms 19,820 KB
testcase_21	AC	403 ms 31,548 KB
testcase_22	AC	13 ms 19,892 KB
testcase_23	AC	13 ms 19,900 KB
testcase_24	AC	551 ms 40,244 KB
testcase_25	AC	13 ms 19,880 KB
testcase_26	AC	13 ms 19,864 KB
testcase_27	AC	13 ms 19,924 KB
testcase_28	AC	14 ms 19,892 KB
testcase_29	AC	674 ms 34,244 KB
testcase_30	AC	625 ms 33,984 KB
testcase_31	AC	412 ms 31,308 KB
testcase_32	AC	280 ms 30,176 KB
testcase_33	AC	13 ms 19,864 KB
testcase_34	AC	14 ms 19,892 KB
testcase_35	AC	229 ms 36,720 KB
testcase_36	AC	144 ms 33,852 KB
testcase_37	AC	13 ms 19,880 KB
testcase_38	AC	585 ms 34,076 KB
testcase_39	AC	13 ms 19,896 KB
testcase_40	AC	622 ms 33,988 KB
testcase_41	AC	268 ms 34,188 KB
testcase_42	AC	268 ms 33,944 KB
testcase_43	AC	273 ms 34,012 KB
testcase_44	AC	284 ms 33,876 KB
testcase_45	AC	633 ms 34,192 KB
testcase_46	AC	536 ms 33,988 KB
testcase_47	AC	639 ms 33,936 KB
testcase_48	AC	541 ms 33,924 KB
testcase_49	AC	14 ms 19,756 KB
testcase_50	AC	14 ms 19,824 KB
testcase_51	AC	14 ms 19,824 KB
testcase_52	AC	13 ms 19,816 KB
testcase_53	AC	13 ms 19,812 KB

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

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード