結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2019-03-28 15:56:55 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 303 ms / 2,000 ms |
コード長 | 6,844 bytes |
コンパイル時間 | 462 ms |
コンパイル使用メモリ | 33,968 KB |
実行使用メモリ | 24,804 KB |
最終ジャッジ日時 | 2024-10-13 04:45:21 |
合計ジャッジ時間 | 2,956 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
#include <float.h>#include <limits.h>#include <math.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <time.h>// 内部定数#define D_VTX_MAX 100000 // 最大頂点数#define D_EDGE_MAX D_VTX_MAX // 最大辺数#define D_LEN_MAX 20 // 最大距離情報数// 内部構造体 - 辺情報typedef struct Edge {int miVNo; // 接続先頂点struct Edge *mzpNext; // 次の辺情報} Edge;// 内部構造体 - 距離情報typedef struct Len {int miVNo; // 頂点int miTax; // 税合計} Len;// 内部構造体 - 頂点情報typedef struct Vtx {Edge *mzpEdge; // 辺int miTax; // 税int miHeight; // 高さ 1~Len mz1Len[D_LEN_MAX]; // 距離情報int miLCnt; // 距離情報数} Vtx;// 内部変数static FILE *szpFpI; // 入力static Vtx sz1Vtx[D_VTX_MAX]; // 頂点static int siVCnt; // 頂点数static Edge sz1Edge[D_EDGE_MAX * 2]; // 辺static int siECnt; // 辺数static long long slSum; // 合計額// 内部変数 - テスト用#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;}// 高さ - セットintfSetHeight(int piVNo // <I> 頂点 0~, int piHeight // <I> 高さ 1~){// セット済if (sz1Vtx[piVNo].miHeight > 0) {return 0;}sz1Vtx[piVNo].miHeight = piHeight;// 辺でループEdge *lzpEdge = sz1Vtx[piVNo].mzpEdge;while (lzpEdge != NULL) {// 下位へfSetHeight(lzpEdge->miVNo, piHeight + 1);// 次の辺へlzpEdge = lzpEdge->mzpNext;}return 0;}// 距離情報 - セット - 1つ目intfSetLen1(){int i;for (i = 1; i < siVCnt; i++) {// 上の頂点 - 取得int liVNo;Edge *lzpEdge = sz1Vtx[i].mzpEdge;while (lzpEdge != NULL) {liVNo = lzpEdge->miVNo;// 高さ - チェックif (sz1Vtx[liVNo].miHeight == sz1Vtx[i].miHeight - 1) {break;}// 次の辺へlzpEdge = lzpEdge->mzpNext;}// 距離情報 - セットsz1Vtx[i].mz1Len[0].miVNo = liVNo;sz1Vtx[i].mz1Len[0].miTax = sz1Vtx[i].miTax;sz1Vtx[i].miLCnt = 1;}return 0;}// 距離情報 - セット - 2つ目以降intfSetLen2(int piLNo // <I> 距離情報 1~){int i;int liSCnt = 0;for (i = 1; i < siVCnt; i++) {// データ有無if (sz1Vtx[i].miLCnt < piLNo) {continue;}// 上の頂点int liVNo = sz1Vtx[i].mz1Len[piLNo - 1].miVNo;// データ有無if (sz1Vtx[liVNo].miLCnt < piLNo) {continue;}// 距離情報 - セットsz1Vtx[i].mz1Len[piLNo].miVNo = sz1Vtx[liVNo].mz1Len[piLNo - 1].miVNo;sz1Vtx[i].mz1Len[piLNo].miTax = sz1Vtx[i].mz1Len[piLNo - 1].miTax + sz1Vtx[liVNo].mz1Len[piLNo - 1].miTax;sz1Vtx[i].miLCnt++;liSCnt++;}return liSCnt;}// 頂点移動intfMove(int *pipVNo // <IO> 頂点, int piMove // <I> 移動量, int piHCnt // <I> 人数){int i;// 移動while (piMove > 0) {// 移動先 - 取得int liMove;for (i = sz1Vtx[*pipVNo].miLCnt - 1; i >= 0; i--) {liMove = 1 << i;if (piMove >= liMove) {break;}}// 移動piMove -= liMove;slSum += sz1Vtx[*pipVNo].mz1Len[i].miTax * piHCnt;*pipVNo = sz1Vtx[*pipVNo].mz1Len[i].miVNo;}return 0;}// 実行メインintfMain(){int i, j, liRet;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);// 辺 - 追加fAddEdge(liVNo1, liVNo2);fAddEdge(liVNo2, liVNo1);}// 税 - 取得for (i = 0; i < siVCnt; i++) {fgets(lc1Buf, sizeof(lc1Buf), szpFpI);sscanf(lc1Buf, "%d", &sz1Vtx[i].miTax);}// 高さ - セットfSetHeight(0, 1);// 距離情報 - セット - 1つ目fSetLen1();// 距離情報 - セット - 2つ目以降for (i = 1; ; i++) {liRet = fSetLen2(i);if (liRet < 1) {break;}}// 行商データ数 - 取得int liDCnt;fgets(lc1Buf, sizeof(lc1Buf), szpFpI);sscanf(lc1Buf, "%d", &liDCnt);// 行商データ - 取得for (i = 0; i < liDCnt; i++) {int liVNo1, liVNo2, liHCnt;fgets(lc1Buf, sizeof(lc1Buf), szpFpI);sscanf(lc1Buf, "%d%d%d", &liVNo1, &liVNo2, &liHCnt);// 高さを揃えるif (sz1Vtx[liVNo1].miHeight < sz1Vtx[liVNo2].miHeight) {fMove(&liVNo2, sz1Vtx[liVNo2].miHeight - sz1Vtx[liVNo1].miHeight, liHCnt);}else if (sz1Vtx[liVNo1].miHeight > sz1Vtx[liVNo2].miHeight) {fMove(&liVNo1, sz1Vtx[liVNo1].miHeight - sz1Vtx[liVNo2].miHeight, liHCnt);}// 頂点を一致させるwhile (liVNo1 != liVNo2) {// 移動先 - 取得for (j = sz1Vtx[liVNo1].miLCnt - 1; j >= 0; j--) {if (sz1Vtx[liVNo1].mz1Len[j].miVNo != sz1Vtx[liVNo2].mz1Len[j].miVNo) {break;}}if (j < 0) {j = 0;}// 移動fMove(&liVNo1, 1 << j, liHCnt);fMove(&liVNo2, 1 << j, liHCnt);}// 合計額 - 加算slSum += sz1Vtx[liVNo1].miTax * liHCnt;}return 0;}// 1回実行intfOne(){int liRet;char lc1Buf[1024];// データ - 初期化memset(sz1Vtx, 0, sizeof(sz1Vtx)); // 頂点siECnt = 0; // 辺数slSum = 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();// 結果 - セットsprintf(lc1Buf, "%lld\n", slSum);// 結果 - 出力fOut(lc1Buf);// 残データ有無#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;}