結果

問題 No.386 貪欲な領主
ユーザー asugen0402
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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_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;
}
// -
int
fAddEdge(
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;
}
// -
int
fSetHeight(
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;
}
// - -
int
fSetLen1(
)
{
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;
}
// - -
int
fSetLen2(
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;
}
//
int
fMove(
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;
}
//
int
fMain(
)
{
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);
// - -
fSetLen1();
// - -
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;
}
//
int
fOne(
)
{
int liRet;
char lc1Buf[1024];
// -
memset(sz1Vtx, 0, sizeof(sz1Vtx)); //
siECnt = 0; //
slSum = 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
//
liRet = fMain();
// -
sprintf(lc1Buf, "%lld\n", slSum);
// -
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