結果

問題 No.614 壊れたキャンパス
ユーザー asugen0402
提出日時 2019-04-19 16:29:52
言語 C
(gcc 13.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0