結果

問題 No.1600 Many Shortest Path Problems
コンテスト
ユーザー 👑 ygussany
提出日時 2021-05-12 09:48:39
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 4,745 bytes
コンパイル時間 360 ms
コンパイル使用メモリ 34,792 KB
実行使用メモリ 40,192 KB
最終ジャッジ日時 2024-07-01 14:25:17
合計ジャッジ時間 18,004 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39 WA * 12
権限があれば一括ダウンロードができます

ソースコード

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