結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2019-03-19 15:38:06 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 69 ms / 3,000 ms |
コード長 | 4,966 bytes |
コンパイル時間 | 365 ms |
コンパイル使用メモリ | 32,128 KB |
実行使用メモリ | 12,032 KB |
最終ジャッジ日時 | 2024-09-13 22:30:23 |
合計ジャッジ時間 | 2,300 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#include <float.h>#include <limits.h>#include <math.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <time.h>// 内部定数#define D_ON 1 // 汎用フラグ - ON#define D_OFF 0 // 汎用フラグ - OFF#define D_VTX_MAX 100000 // 最大頂点数#define D_EDGE_MAX 200000 // 最大辺数// 内部構造体 - 辺情報typedef struct Edge {int miVNo; // 接続先頂点struct Edge *mzpNext; // 次の辺情報} Edge;// 内部構造体 - 頂点情報typedef struct Vtx {Edge *mzpEdge; // 辺int miRLen; // 根からの距離int miLDLen; // 葉(下)からの距離int miLLen; // 一番近い葉からの距離int miDone; // 処理済フラグ} Vtx;// 内部変数static FILE *szpFpI; // 入力static Vtx sz1Vtx[D_VTX_MAX]; // 頂点static int siVCnt; // 頂点数static Edge sz1Edge[D_EDGE_MAX * 2]; // 辺static int siECnt; // 辺数// 内部変数 - テスト用#ifdef D_TESTstatic int siRes;static FILE *szpFpA;static int siTNo;#endif// 出力intfOut(char *pcpLine // <I> 1行){char lc1Buf[1024];#ifdef D_TESTfgets(lc1Buf, sizeof(lc1Buf), szpFpA);if (strcmp(lc1Buf, pcpLine)) {siRes = -1;}#elseprintf("%s", pcpLine);#endifreturn 0;}// 辺 - 追加intfAddEdge(int piVFNo // <I> 頂点 - 元 0~, int piVTNo // <I> 頂点 - 先 0~){sz1Edge[siECnt].miVNo = piVTNo;sz1Edge[siECnt].mzpNext = sz1Vtx[piVFNo].mzpEdge;sz1Vtx[piVFNo].mzpEdge = &sz1Edge[siECnt];siECnt++;return 0;}// 距離 - セットintfSetLen(int piVNo // <I> 頂点 0~, int piRLen // <I> 根からの距離 0~){// 処理済フラグif (sz1Vtx[piVNo].miDone != D_OFF) {return -1;}sz1Vtx[piVNo].miDone = D_ON;// 根からの距離 - セットsz1Vtx[piVNo].miRLen = piRLen;// 辺でループint liMin = INT_MAX;Edge *lzpEdge = sz1Vtx[piVNo].mzpEdge;while (lzpEdge != NULL) {// 葉(下)からの距離 - 取得int liLen = fSetLen(lzpEdge->miVNo, piRLen + 1);if (liLen >= 0) {if (liMin > liLen) {liMin = liLen;}}// 次の辺へlzpEdge = lzpEdge->mzpNext;}// 葉(下)からの距離 - セットif (liMin == INT_MAX) {liMin = 0;}sz1Vtx[piVNo].miLDLen = liMin;return liMin + 1;}// 一番近い葉からの距離 - セットintfSetLLen(int piVNo // <I> 頂点 0~, int piLLen // <I> 一番近い葉からの距離 0~){// 処理済フラグif (sz1Vtx[piVNo].miDone != D_OFF) {return -1;}sz1Vtx[piVNo].miDone = D_ON;// 一番近い葉からの距離int liLLen;if (piLLen < sz1Vtx[piVNo].miLDLen) {liLLen = piLLen;}else {liLLen = sz1Vtx[piVNo].miLDLen;}sz1Vtx[piVNo].miLLen = liLLen;// 辺でループEdge *lzpEdge = sz1Vtx[piVNo].mzpEdge;while (lzpEdge != NULL) {// 下位へfSetLLen(lzpEdge->miVNo, liLLen + 1);// 次の辺へlzpEdge = lzpEdge->mzpNext;}return 0;}// 実行メインintfMain(){int i;char lc1Buf[1024];// 頂点数 - 取得fgets(lc1Buf, sizeof(lc1Buf), szpFpI);sscanf(lc1Buf, "%d", &siVCnt);// 辺 - 取得for (i = 0; i < siVCnt - 1; i++) {int liVNo1, liVNo2;fgets(lc1Buf, sizeof(lc1Buf), szpFpI);sscanf(lc1Buf, "%d%d", &liVNo1, &liVNo2);liVNo1--;liVNo2--;// 辺 - 追加fAddEdge(liVNo1, liVNo2);fAddEdge(liVNo2, liVNo1);}// 距離 - セットfSetLen(0, 0);// 処理済フラグ - 初期化for (i = 0; i < siVCnt; i++) {sz1Vtx[i].miDone = D_OFF;}// 一番近い葉からの距離 - セットfSetLLen(0, INT_MAX);// 距離 - 表示for (i = 0; i < siVCnt; i++) {if (sz1Vtx[i].miRLen < sz1Vtx[i].miLLen) {sprintf(lc1Buf, "%d\n", sz1Vtx[i].miRLen);}else {sprintf(lc1Buf, "%d\n", sz1Vtx[i].miLLen);}fOut(lc1Buf);}return 0;}// 1回実行intfOne(){int liRet;char lc1Buf[1024];// データ - 初期化memset(sz1Vtx, 0, sizeof(sz1Vtx)); // 頂点siECnt = 0; // 辺数// 入力 - セット#ifdef D_TESTsprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);szpFpI = fopen(lc1Buf, "r");sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);szpFpA = fopen(lc1Buf, "r");siRes = 0;#elseszpFpI = stdin;#endif// 実行メインliRet = fMain();// 残データ有無#ifdef D_TESTlc1Buf[0] = '\0';fgets(lc1Buf, sizeof(lc1Buf), szpFpA);if (strcmp(lc1Buf, "")) {siRes = -1;}#endif// テストファイルクローズ#ifdef D_TESTfclose(szpFpI);fclose(szpFpA);#endif// テスト結果#ifdef D_TESTif (siRes == 0) {printf("OK %d\n", siTNo);}else {printf("NG %d\n", siTNo);}#endifreturn 0;}// プログラム開始intmain(){#ifdef D_TESTint i;for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {siTNo = i;fOne();}#elsefOne();#endifreturn 0;}