結果
問題 | No.762 PDCAパス |
ユーザー |
![]() |
提出日時 | 2019-04-25 14:45:33 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 35 ms / 2,000 ms |
コード長 | 4,113 bytes |
コンパイル時間 | 214 ms |
コンパイル使用メモリ | 32,256 KB |
実行使用メモリ | 7,296 KB |
最終ジャッジ日時 | 2024-11-19 05:29:11 |
合計ジャッジ時間 | 2,354 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <float.h>#include <limits.h>#include <math.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <time.h>// 内部定数#define D_MOD 1000000007 // 除数(10の9乗+7)#define D_VTX_MAX 100000 // 最大頂点数#define D_EDGE_MAX 100000 // 最大辺数// 内部構造体 - 辺情報typedef struct Edge {int miVNo; // 接続先頂点struct Edge *mzpNext; // 次の辺情報} Edge;// 内部構造体 - 頂点情報typedef struct Vtx {char mcChar; // 文字long long mlPCnt; // パターン数Edge *mzpEdge; // 辺} 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;}// パターン数 - セットintfSetPCnt(char pcSChar // <I> 開始文字, char pcEChar // <I> 終了文字){int i;for (i = 0; i < siVCnt; i++) {// 開始文字if (sz1Vtx[i].mcChar != pcSChar) {continue;}// 辺でループEdge *lzpEdge = sz1Vtx[i].mzpEdge;while (lzpEdge != NULL) {// 終了文字if (sz1Vtx[lzpEdge->miVNo].mcChar == pcEChar) {sz1Vtx[lzpEdge->miVNo].mlPCnt += sz1Vtx[i].mlPCnt;}// 次の辺へlzpEdge = lzpEdge->mzpNext;}}return 0;}// 実行メインintfMain(){int i;char lc1Buf[1024];// 頂点数・辺数 - 取得int liECnt;fgets(lc1Buf, sizeof(lc1Buf), szpFpI);sscanf(lc1Buf, "%d%d", &siVCnt, &liECnt);// 文字 - 取得for (i = 0; i < siVCnt; i++) {fscanf(szpFpI, "%c", &sz1Vtx[i].mcChar);}fgets(lc1Buf, sizeof(lc1Buf), szpFpI);// 辺 - 取得for (i = 0; i < liECnt; i++) {int liVNo1, liVNo2;fgets(lc1Buf, sizeof(lc1Buf), szpFpI);sscanf(lc1Buf, "%d%d", &liVNo1, &liVNo2);liVNo1--;liVNo2--;// 辺 - 追加fAddEdge(liVNo1, liVNo2);fAddEdge(liVNo2, liVNo1);}// パターン数 - セット - Pfor (i = 0; i < siVCnt; i++) {if (sz1Vtx[i].mcChar == 'P') {sz1Vtx[i].mlPCnt = 1;}}// パターン数 - セットfSetPCnt('P', 'D');fSetPCnt('D', 'C');fSetPCnt('C', 'A');// パターン数 - 合計long long llSum = 0;for (i = 0; i < siVCnt; i++) {if (sz1Vtx[i].mcChar == 'A') {llSum += sz1Vtx[i].mlPCnt;llSum %= D_MOD;}}return (int)llSum;}// 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();// 出力sprintf(lc1Buf, "%d\n", liRet);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;}