結果

問題 No.2179 Planet Traveler
コンテスト
ユーザー 👑 ygussany
提出日時 2023-01-06 22:34:31
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 33 ms / 3,000 ms
コード長 2,532 bytes
コンパイル時間 984 ms
コンパイル使用メモリ 34,176 KB
実行使用メモリ 22,016 KB
最終ジャッジ日時 2024-11-30 18:57:43
合計ジャッジ時間 2,276 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

long double distance(int X1, int Y1, int X2, int Y2)
{
	return sqrtl((long long)(X1 - X2) * (X1 - X2) + (long long)(Y1 - Y2) * (Y1 - Y2));
}

typedef struct {
	long double key;
	int u, w;
} data;

typedef struct {
	data obj[1000001];
	int size;
} min_heap;

void push(min_heap* h, data x)
{
	int i = ++(h->size), j = i >> 1;
	data tmp;
	h->obj[i] = x;
	while (j > 0) {
		if (h->obj[i].key < h->obj[j].key) {
			tmp = h->obj[j];
			h->obj[j] = h->obj[i];
			h->obj[i] = tmp;
			i = j;
			j >>= 1;
		} else break;
	}
}

data pop(min_heap* h)
{
	int i = 1, j = 2;
	data output = h->obj[1], tmp;
	h->obj[1] = h->obj[(h->size)--];
	while (j <= h->size) {
		if (j < h->size && h->obj[j^1].key < h->obj[j].key) j ^= 1;
		if (h->obj[j].key < h->obj[i].key) {
			tmp = h->obj[j];
			h->obj[j] = h->obj[i];
			h->obj[i] = tmp;
			i = j;
			j <<= 1;
		} else break;
	}
	return output;
}

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

void UF_init(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 main()
{
	int i, N, X[801], Y[801], T[801];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d %d %d", &(X[i]), &(Y[i]), &(T[i]));
	
	int j;
	long double dist[801][801];
	for (i = 1; i <= N; i++) {
		for (j = i + 1, dist[i][i] = 0; j <= N; j++) {
			if (T[i] != T[j]) dist[i][j] = fabsl(distance(X[i], Y[i], 0, 0) - distance(X[j], Y[j], 0, 0));
			else dist[i][j] = distance(X[i], Y[i], X[j], Y[j]);
			dist[j][i] = dist[i][j];
		}
	}
	/*
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= N; j++) {
			printf("%Lf ", dist[i][j]);
		}
		printf("\n");
	}
	*/
	
	data d;
	min_heap h;
	UF_forest F;
	UF_init(&F, N);
	h.size = 0;
	for (i = 1; i <= N; i++) {
		for (j = i + 1; j <= N; j++) {
			d.key = dist[i][j];
			d.u = i;
			d.w = j;
			push(&h, d);
		}
	}
	while (UF_root(&F, 1) != UF_root(&F, N)) {
		d = pop(&h);
		i = d.u;
		j = d.w;
		UF_merge(&F, i, j);
	}
	printf("%lld\n", (long long)(d.key * d.key + 0.99999999));
	fflush(stdout);
	return 0;
}
0