結果

問題 No.614 壊れたキャンパス
ユーザー asugen0402asugen0402
提出日時 2019-04-19 16:29:52
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 534 ms / 2,000 ms
コード長 13,713 bytes
コンパイル時間 325 ms
コンパイル使用メモリ 35,200 KB
実行使用メモリ 43,468 KB
最終ジャッジ日時 2024-09-22 11:32:20
合計ジャッジ時間 7,248 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
14,196 KB
testcase_01 AC 3 ms
14,196 KB
testcase_02 AC 3 ms
14,068 KB
testcase_03 AC 4 ms
14,192 KB
testcase_04 AC 4 ms
14,196 KB
testcase_05 AC 3 ms
14,192 KB
testcase_06 AC 4 ms
14,196 KB
testcase_07 AC 3 ms
14,320 KB
testcase_08 AC 442 ms
43,060 KB
testcase_09 AC 496 ms
42,000 KB
testcase_10 AC 403 ms
41,916 KB
testcase_11 AC 485 ms
43,152 KB
testcase_12 AC 534 ms
41,756 KB
testcase_13 AC 504 ms
42,104 KB
testcase_14 AC 459 ms
43,468 KB
testcase_15 AC 347 ms
42,340 KB
testcase_16 AC 399 ms
42,048 KB
testcase_17 AC 176 ms
37,592 KB
testcase_18 AC 189 ms
41,408 KB
testcase_19 AC 165 ms
39,796 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// 内部定数
#define D_MOVE_MAX		200000									// 最大移動数
#define D_TREE_MAX		400005									// 木の最大データ数
#define D_TREE_WCNT		2										// 木の方向数
#define D_TREE_LEFT		0										// 木の方向 - 左側
#define D_TREE_RIGHT	1										// 木の方向 - 右側
#define D_VTX_MAX		D_TREE_MAX								// 最大頂点数
#define D_EDGE_MAX		500005									// 最大辺数
#define D_HEAP_MAX		D_VTX_MAX								// 最大ヒープ数

// 内部構造体 - 移動情報
typedef struct Move {
	int miBNo;													// 建物 1～
	int miFVal;													// 移動元階
	int miTVal;													// 移動先階
} Move;

// 内部構造体 - 木構造
typedef struct Tree {
	int miBNo;													// 建物 1～
	int miVal;													// 階 1～
	int miVNo;													// 頂点番号 0～
	int mi1Height[D_TREE_WCNT];									// 木の高さ
	struct Tree *mzp1Child[D_TREE_WCNT];						// 子
} Tree;

// 内部構造体 - 辺情報
typedef struct Edge {
	int miVNo;													// 接続先頂点
	int miVal;													// 階差
	struct Edge *mzpNext;										// 次の辺情報
} Edge;

// 内部構造体 - 頂点情報
typedef struct Vtx {
	Edge *mzpEdge;												// 辺
	long long mlSum;											// 階合計
} Vtx;

// 内部構造体 - ヒープ情報
typedef struct Heap {
	long long mlSum;											// 階合計
	int miVNo;													// 頂点番号 0～
} Heap;

// 内部変数
static FILE *szpFpI;											// 入力
static int siBCnt;												// 建物数
static Move sz1Move[D_MOVE_MAX];								// 移動情報
static int siMCnt;												// 移動情報数
static Tree sz1Tree[D_TREE_MAX];								// 木の実データ
static int siTCnt;												// 木の実データ数
static Tree *szpTop;											// 先頭の木データ
static Tree *szpTPre;											// １つ前の木データ
static Vtx sz1Vtx[D_VTX_MAX];									// 頂点
static int siVCnt;												// 頂点数
static Edge sz1Edge[D_EDGE_MAX * 2];							// 辺
static int siECnt;												// 辺数
static Heap sz1Heap[D_HEAP_MAX];								// ヒープ
static int siHCnt;												// ヒープ数

// 内部変数 - テスト用
#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;
}

// 木データ - 作成
Tree *
fTreeMake(
	int piBNo					// <I> 建物 1～
	, int piVal					// <I> 階 1～
	, int piVNo					// <I> 頂点番号 0～
)
{
	// 対象の木データ
	Tree *lzpTree = &(sz1Tree[siTCnt]);
	siTCnt++;

	// データセット
	memset(lzpTree, 0, sizeof(Tree));		// 初期化
	lzpTree->miBNo = piBNo;					// 建物
	lzpTree->miVal = piVal;					// 階
	lzpTree->miVNo = piVNo;					// 頂点番号

	return lzpTree;
}

// 木データ - 比較 - 建物昇順 - 階昇順
int
fTreeCmp(
	Tree *pzpTree				// <I> 木データ
	, int piBNo					// <I> 建物 1～
	, int piVal					// <I> 階 1～
)
{
	// 建物昇順
	if (piBNo < pzpTree->miBNo) {			// 左側
		return -1;
	}
	else if (piBNo > pzpTree->miBNo) {		// 右側
		return 1;
	}

	// 階昇順
	if (piVal < pzpTree->miVal) {			// 左側
		return -1;
	}
	else if (piVal > pzpTree->miVal) {		// 右側
		return 1;
	}

	return 0;
}

// 木データ - 検索
Tree *
fTreeSrh(
	int piBNo					// <I> 建物 1～
	, int piVal					// <I> 階 1～
)
{
	// 先頭の木データ
	Tree *lzpNow = szpTop;

	// 検索
	while (1) {

		// データ有無
		if (lzpNow == NULL) {
			return NULL;
		}

		// 比較
		int liRet = fTreeCmp(lzpNow, piBNo, piVal);
		if (liRet == 0) {								// 一致
			return lzpNow;
		}

		// 子へ移動
		if (liRet < 0) {								// 左側
			lzpNow = lzpNow->mzp1Child[D_TREE_LEFT];
		}
		else {											// 右側
			lzpNow = lzpNow->mzp1Child[D_TREE_RIGHT];
		}
	}

	return NULL;
}

// 木データ - 高さ取得
int
fTreeGetHeight(
	Tree *pzpTree				// <I> 対象の木情報
)
{
	// データ有無
	if (pzpTree == NULL) {
		return 0;
	}

	if (pzpTree->mi1Height[D_TREE_LEFT] >= pzpTree->mi1Height[D_TREE_RIGHT]) {
		return pzpTree->mi1Height[D_TREE_LEFT] + 1;
	}
	else {
		return pzpTree->mi1Height[D_TREE_RIGHT] + 1;
	}
}

// 木データ - 右回転(親は子の右下へ・子は親の左上へ)
int
fTreeRttR(
	Tree **pzppTree				// <I> 回転対象
)
{
	// 現在の子
	Tree *lzpChild = (*pzppTree)->mzp1Child[D_TREE_LEFT];

	// 右回転
	(*pzppTree)->mzp1Child[D_TREE_LEFT] = lzpChild->mzp1Child[D_TREE_RIGHT];	// 親の左側 = 子の右側
	(*pzppTree)->mi1Height[D_TREE_LEFT] = lzpChild->mi1Height[D_TREE_RIGHT];	// 親の高さ(左) = 子の高さ(右)
	lzpChild->mzp1Child[D_TREE_RIGHT] = *pzppTree;								// 子の右側 = 親
	lzpChild->mi1Height[D_TREE_RIGHT] = fTreeGetHeight(*pzppTree);				// 子の高さ(右) - 親の高さ
	*pzppTree = lzpChild;														// 親 = 子

	return 0;
}

// 木データ - 左回転(親は子の左下へ・子は親の右上へ)
int
fTreeRttL(
	Tree **pzppTree				// <I> 回転対象
)
{
	// 現在の子
	Tree *lzpChild = (*pzppTree)->mzp1Child[D_TREE_RIGHT];

	// 左回転
	(*pzppTree)->mzp1Child[D_TREE_RIGHT] = lzpChild->mzp1Child[D_TREE_LEFT];	// 親の右側 = 子の左側
	(*pzppTree)->mi1Height[D_TREE_RIGHT] = lzpChild->mi1Height[D_TREE_LEFT];	// 親の高さ(右) = 子の高さ(左)
	lzpChild->mzp1Child[D_TREE_LEFT] = *pzppTree;								// 子の左側 = 親
	lzpChild->mi1Height[D_TREE_LEFT] = fTreeGetHeight(*pzppTree);				// 子の高さ(左) - 親の高さ
	*pzppTree = lzpChild;														// 親 = 子

	return 0;
}

// 木データ - 追加・削除の共通処理
// 戻り値：[1]高さの変更あり [0]高さの変更なし
int
fTreeComAddDel(
	Tree **pzppNow				// <I> 現在の木情報
	, int piWay					// <I> 対象の方向
)
{
	// 高さの変更があるかチェック
	int liNew = fTreeGetHeight((*pzppNow)->mzp1Child[piWay]);
	if ((*pzppNow)->mi1Height[piWay] == liNew) {												// 変化なし
		return 0;
	}
	(*pzppNow)->mi1Height[piWay] = liNew;														// 更新

	// 高さが離れている場合、回転
	if ((*pzppNow)->mi1Height[D_TREE_LEFT] - (*pzppNow)->mi1Height[D_TREE_RIGHT] > 1) {			// 左側が高い
		fTreeRttR(pzppNow);																			// 右回転
	}
	else if ((*pzppNow)->mi1Height[D_TREE_RIGHT] - (*pzppNow)->mi1Height[D_TREE_LEFT] > 1) {	// 右側が高い
		fTreeRttL(pzppNow);																			// 左回転
	}

	return 1;
}

// 木データ - 追加
// 戻り値：[1]高さの変更あり [0]高さの変更なし [-1]追加なし
int
fTreeAdd(
	Tree **pzppNow				// <I> 現在の木情報
	, int piBNo					// <I> 建物 1～
	, int piVal					// <I> 階 1～
	, int piVNo					// <I> 頂点番号 0～
)
{
	// 作成
	if (*pzppNow == NULL) {
		*pzppNow = fTreeMake(piBNo, piVal, piVNo);
		return 1;
	}

	// 比較
	int liRet = fTreeCmp(*pzppNow, piBNo, piVal);

	// 一致
	if (liRet == 0) {
		return -1;
	}

	// 方向の判別
	int liWay;
	if (liRet < 0) {															// 左側
		liWay = D_TREE_LEFT;
	}
	else {																		// 右側
		liWay = D_TREE_RIGHT;
	}

	// 下位へ
	liRet = fTreeAdd(&((*pzppNow)->mzp1Child[liWay]), piBNo, piVal, piVNo);
	if (liRet < 1) {															// 高さの変更なし or 追加なし
		return liRet;
	}

	// 追加・削除の共通処理
	return fTreeComAddDel(pzppNow, liWay);
}

// 辺 - 追加
int
fAddEdge(
	int piVFNo					// <I> 頂点 - 元 0～
	, int piVTNo				// <I> 頂点 - 先 0～
	, int piVal					// <I> 階差 0～
)
{
	sz1Edge[siECnt].miVNo = piVTNo;
	sz1Edge[siECnt].miVal = piVal;
	sz1Edge[siECnt].mzpNext = sz1Vtx[piVFNo].mzpEdge;
	sz1Vtx[piVFNo].mzpEdge = &sz1Edge[siECnt];
	siECnt++;

	return 0;
}

// 同一建物内の頂点を辺で結合
int
fTreeVNoConv(
	Tree *pzpNow				// <I> 現在の木情報
)
{
	// データ有無
	if (pzpNow == NULL) {
		return 0;
	}

	// 左側
	fTreeVNoConv(pzpNow->mzp1Child[D_TREE_LEFT]);

	// １つ前の木データ
	if (szpTPre != NULL) {
		if (szpTPre->miBNo == pzpNow->miBNo) {
			int liVal = abs(szpTPre->miVal - pzpNow->miVal);
			fAddEdge(szpTPre->miVNo, pzpNow->miVNo, liVal);
			fAddEdge(pzpNow->miVNo, szpTPre->miVNo, liVal);
		}
	}
	szpTPre = pzpNow;

	// 右側
	fTreeVNoConv(pzpNow->mzp1Child[D_TREE_RIGHT]);

	return 0;
}

// ヒープ - 比較 - 階合計昇順
int
fHeapCmp(
	int piNo1					// <I> 配列番号１ 0～
	, int piNo2					// <I> 配列番号２ 0～
)
{
	// 階合計昇順
	if (sz1Heap[piNo1].mlSum < sz1Heap[piNo2].mlSum) {
		return -1;
	}
	else if (sz1Heap[piNo1].mlSum > sz1Heap[piNo2].mlSum) {
		return 1;
	}

	return 0;
}

// ヒープ - 親子関係チェック
// 戻り値：[>=0]:変更した子の配列番号 [-1]:変更なし
int
fHeapChk(
	int piPNo					// <I> 親の配列番号 0～
)
{
	int liRet;

	// 最小値
	int liMNo = piPNo;

	// 左の子と比較
	int liCNo = piPNo * 2 + 1;
	if (liCNo < siHCnt) {
		liRet = fHeapCmp(liMNo, liCNo);
		if (liRet == 1) {
			liMNo = liCNo;
		}
	}

	// 右の子と比較
	liCNo = piPNo * 2 + 2;
	if (liCNo < siHCnt) {
		liRet = fHeapCmp(liMNo, liCNo);
		if (liRet == 1) {
			liMNo = liCNo;
		}
	}

	// 自分が最小値であるかチェック
	if (piPNo == liMNo) {
		return -1;
	}

	// 値の交換
	Heap lzWork;
	memcpy(&lzWork, &sz1Heap[liMNo], sizeof(Heap));
	memcpy(&sz1Heap[liMNo], &sz1Heap[piPNo], sizeof(Heap));
	memcpy(&sz1Heap[piPNo], &lzWork, sizeof(Heap));

	return liMNo;
}

// ヒープ - キュー追加
int
fHeapEnqueue(
	long long plSum				// <I> 階合計
	, int piVNo					// <I> 頂点番号 0～
)
{
	int liRet;

	// 階合計 - チェック
	if (sz1Vtx[piVNo].mlSum <= plSum) {
		return 0;
	}
	sz1Vtx[piVNo].mlSum = plSum;

	// 末尾に追加
	sz1Heap[siHCnt].mlSum = plSum;
	sz1Heap[siHCnt].miVNo = piVNo;
	siHCnt++;

	// 親子関係チェック
	int liNo = siHCnt - 1;
	while (1) {

		// 親の配列番号
		liNo = (liNo - 1) / 2;

		// 親子関係チェック
		liRet = fHeapChk(liNo);
		if (liRet < 0) {
			break;
		}
	}

	return 0;
}

// ヒープ - キュー取得
int
fHeapDequeue(
	Heap *pzpRet				// <O> 取得先
)
{
	// データ数
	if (siHCnt < 1) {
		return -1;
	}

	// 取得
	memcpy(pzpRet, &sz1Heap[0], sizeof(Heap));
	siHCnt--;

	// データ数
	if (siHCnt < 1) {
		return 0;
	}

	// 末尾を先頭へ
	memcpy(&sz1Heap[0], &sz1Heap[siHCnt], sizeof(Heap));

	// 親子関係チェック
	int liNo = 0;
	while (liNo >= 0) {
		liNo = fHeapChk(liNo);
	}

	return 0;
}

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

	// 建物数・移動情報数・開始階・終了階 - 取得
	int liSVal, liEVal;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d%d%d%d", &siBCnt, &siMCnt, &liWork, &liSVal, &liEVal);

	// 開始階・終了階の頂点登録
	fTreeAdd(&szpTop, 1, liSVal, 0);
	fTreeAdd(&szpTop, siBCnt, liEVal, 1);
	siVCnt = 2;

	// 移動情報 - 取得
	for (i = 0; i < siMCnt; i++) {
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d%d%d", &sz1Move[i].miBNo, &sz1Move[i].miFVal, &sz1Move[i].miTVal);

		// 頂点登録
		liRet = fTreeAdd(&szpTop, sz1Move[i].miBNo, sz1Move[i].miFVal, siVCnt);
		if (liRet >= 0) {
			siVCnt++;
		}
		liRet = fTreeAdd(&szpTop, sz1Move[i].miBNo + 1, sz1Move[i].miTVal, siVCnt);
		if (liRet >= 0) {
			siVCnt++;
		}
	}

	// 頂点 - 初期化
	for (i = 0; i < siVCnt; i++) {
		sz1Vtx[i].mlSum = LLONG_MAX;
	}

	// 同一建物内の頂点を辺で結合
	szpTPre = NULL;
	fTreeVNoConv(szpTop);

	// 移動情報で頂点を辺で結合
	for (i = 0; i < siMCnt; i++) {
		Tree *lzpFrom = fTreeSrh(sz1Move[i].miBNo, sz1Move[i].miFVal);
		Tree *lzpTo = fTreeSrh(sz1Move[i].miBNo + 1, sz1Move[i].miTVal);
		fAddEdge(lzpFrom->miVNo, lzpTo->miVNo, 0);
	}

	// ヒープ - 初期値
	fHeapEnqueue(0, 0);

	// 頂点 - 移動
	while (1) {

		// ヒープ - 取得
		Heap lzHeap;
		liRet = fHeapDequeue(&lzHeap);
		if (liRet != 0) {
			break;
		}

		// 辺でループ
		Edge *lzpEdge = sz1Vtx[lzHeap.miVNo].mzpEdge;
		while (lzpEdge != NULL) {

			// ヒープ - 追加
			fHeapEnqueue(lzHeap.mlSum + (long long)lzpEdge->miVal, lzpEdge->miVNo);

			// 次の辺へ
			lzpEdge = lzpEdge->mzpNext;
		}
	}

	// 到着チェック
	if (sz1Vtx[1].mlSum == LLONG_MAX) {
		return -1;
	}
	else {
		return sz1Vtx[1].mlSum;
	}
}

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

	// データ - 初期化
	siTCnt = 0;													// 木の実データ数
	szpTop = NULL;												// 先頭の木データ
	memset(sz1Vtx, 0, sizeof(sz1Vtx));							// 頂点
	siECnt = 0;													// 辺数
	siHCnt = 0;													// ヒープ数

	// 入力 - セット
#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

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

	// 出力
	sprintf(lc1Buf, "%lld\n", llRet);
	fOut(lc1Buf);

	// 残データ有無
#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