結果

問題 No.416 旅行会社
ユーザー asugen0402
提出日時 2019-04-05 11:15:20
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 239 ms / 4,000 ms
コード長 5,889 bytes
コンパイル時間 306 ms
コンパイル使用メモリ 33,536 KB
実行使用メモリ 8,116 KB
最終ジャッジ日時 2024-12-14 20:36:09
合計ジャッジ時間 3,943 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_ILD_MAX		100000									// 最大島数
#define D_BRD_MAX		200000									// 最大橋数

// 内部構造体 - 島情報
typedef struct Ild {
	int miPrev;													// 前の島 - 0～
	int miNext;													// 次の島 - 0～
	int miGNo;													// グループ番号 0～
	int miENo;													// イベント番号 -1～
} Ild;

// 内部構造体 - 橋情報
typedef struct Brd {
	int miINo1;													// 島１ 0～
	int miINo2;													// 島２ 0～
	int miENo;													// イベント番号 1～
} Brd;

// 内部変数
static FILE *szpFpI;											// 入力
static Ild sz1Ild[D_ILD_MAX];									// 島
static int siICnt;												// 島数
static Brd sz1Brd[D_BRD_MAX];									// 橋
static int siBCnt;												// 橋数

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// 出力
int
fOut(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// 橋 - ソート関数 - 島１昇順 - 島２昇順
int
fSortFncBrdIU(
	const void *pzpVal1			// <I> 値１
	, const void *pzpVal2		// <I> 値２
)
{
	Brd *lzpVal1 = (Brd *)pzpVal1;
	Brd *lzpVal2 = (Brd *)pzpVal2;

	// 島１昇順
	if (lzpVal1->miINo1 > lzpVal2->miINo1) {
		return 1;
	}
	else if (lzpVal1->miINo1 < lzpVal2->miINo1) {
		return -1;
	}

	// 島２昇順
	if (lzpVal1->miINo2 > lzpVal2->miINo2) {
		return 1;
	}
	else if (lzpVal1->miINo2 < lzpVal2->miINo2) {
		return -1;
	}

	return 0;
}

// 橋 - ソート関数 - イベント番号降順
int
fSortFncBrdED(
	const void *pzpVal1			// <I> 値１
	, const void *pzpVal2		// <I> 値２
)
{
	Brd *lzpVal1 = (Brd *)pzpVal1;
	Brd *lzpVal2 = (Brd *)pzpVal2;

	// イベント番号降順
	if (lzpVal1->miENo > lzpVal2->miENo) {
		return -1;
	}
	else if (lzpVal1->miENo < lzpVal2->miENo) {
		return 1;
	}

	return 0;
}

// 島 - グループ番号 - 取得
int
fIldGetGNo(
	int piINo					// <I> 島 0～
)
{
	if (sz1Ild[piINo].miGNo == piINo) {
		return piINo;
	}

	// 取得・更新
	sz1Ild[piINo].miGNo = fIldGetGNo(sz1Ild[piINo].miGNo);

	return sz1Ild[piINo].miGNo;
}

// 島 - イベント番号 - セット
int
fIldSetENo(
	int piINo					// <I> 島 0～
	, int piENo					// <I> イベント番号 -1～
)
{
	int liINo = piINo;
	while (1) {
		sz1Ild[liINo].miENo = piENo;		// セット
		liINo = sz1Ild[liINo].miNext;		// 次へ
		if (liINo == piINo) {
			break;
		}
	}

	return 0;
}

// 島 - 連結
int
fIldConv(
	int piINo1					// <I> 島１ 0～
	, int piINo2				// <I> 島２ 0～
	, int piENo					// <I> イベント番号 -1～
)
{
	// グループ番号
	int liGNo1 = fIldGetGNo(piINo1);
	int liGNo2 = fIldGetGNo(piINo2);
	if (liGNo1 == liGNo2) {
		return 0;
	}
	sz1Ild[liGNo2].miGNo = liGNo1;

	// 島 - イベント番号 - セット
	if (sz1Ild[piINo1].miENo != 0) {
		fIldSetENo(piINo2, piENo);
	}
	else if (sz1Ild[piINo2].miENo != 0) {
		fIldSetENo(piINo1, piENo);
	}

	// 次の前・前の次
	int liINo1 = sz1Ild[piINo1].miNext;
	int liINo2 = sz1Ild[piINo2].miPrev;
	sz1Ild[liINo1].miPrev = liINo2;
	sz1Ild[liINo2].miNext = liINo1;

	// 次・前
	sz1Ild[piINo2].miPrev = piINo1;
	sz1Ild[piINo1].miNext = piINo2;

	return 0;
}

// 実行メイン
int
fMain(
)
{
	int i;
	char lc1Buf[1024];

	// 島数・橋数・イベント数 - 取得
	int liECnt;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d%d", &siICnt, &siBCnt, &liECnt);

	// 島 - 初期化
	for (i = 0; i < siICnt; i++) {
		sz1Ild[i].miPrev = i;
		sz1Ild[i].miNext = i;
		sz1Ild[i].miGNo = i;
	}
	sz1Ild[0].miENo = -1;

	// 橋 - 取得
	for (i = 0; i < siBCnt; i++) {
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d%d", &sz1Brd[i].miINo1, &sz1Brd[i].miINo2);
		sz1Brd[i].miINo1--;
		sz1Brd[i].miINo2--;
		sz1Brd[i].miENo = INT_MAX;
	}

	// 橋 - ソート
	qsort(sz1Brd, siBCnt, sizeof(Brd), fSortFncBrdIU);

	// イベント - 取得
	for (i = 0; i < liECnt; i++) {
		Brd lzBrd;
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d%d", &lzBrd.miINo1, &lzBrd.miINo2);
		lzBrd.miINo1--;
		lzBrd.miINo2--;

		// 対象の橋
		Brd *lzpBrd = (Brd *)bsearch(&lzBrd, sz1Brd, siBCnt, sizeof(Brd), fSortFncBrdIU);
		lzpBrd->miENo = i + 1;
	}

	// 橋 - ソート
	qsort(sz1Brd, siBCnt, sizeof(Brd), fSortFncBrdED);

	// 残る橋で島を連結
	for (i = 0; i < siBCnt - liECnt; i++) {
		fIldConv(sz1Brd[i].miINo1, sz1Brd[i].miINo2, -1);
	}

	// 橋を作成
	for ( ; i < siBCnt; i++) {
		fIldConv(sz1Brd[i].miINo1, sz1Brd[i].miINo2, sz1Brd[i].miENo);
	}

	// 出力
	for (i = 1; i < siICnt; i++) {
		sprintf(lc1Buf, "%d\n", sz1Ild[i].miENo);
		fOut(lc1Buf);
	}

	return 0;
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// データ - 初期化
	memset(sz1Ild, 0, sizeof(sz1Ild));							// 島

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}
0