結果

問題 No.386 貪欲な領主
ユーザー haruteruharuteru
提出日時 2016-07-05 11:28:59
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,392 bytes
コンパイル時間 596 ms
コンパイル使用メモリ 62,888 KB
実行使用メモリ 25,120 KB
最終ジャッジ日時 2024-04-20 21:59:43
合計ジャッジ時間 4,304 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
12,800 KB
testcase_01 AC 5 ms
7,368 KB
testcase_02 AC 6 ms
7,296 KB
testcase_03 AC 6 ms
7,392 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <bitset>
#include <memory.h>
using namespace std;

typedef unsigned long long INT;

#define MAXN (100000+1)
#define MAXM (200000+1)

struct Root {
    int no;
    int cost;
    vector<INT> roots;
};

INT N, M, TOTAL;
Root R[MAXN];
INT memo[MAXN];
bitset<MAXN> bit;

INT fn(INT a, INT b, INT c)
{
    if (memo[a] > 0) {
        return memo[a];
    }
    INT rc;
    if (a == b) {
        rc = R[a].cost * c;
    }
    else {
        rc = -1;
        for (INT n = 0; n < R[a].roots.size(); n++) {
            if (bit.test(R[a].roots[n]) == 0) {
                bit.set(R[a].roots[n]);
                rc = min(rc, fn(R[a].roots[n], b, c));
                bit.reset(R[a].roots[n]);
            }
        }
        if (rc != -1) {
            rc += (R[a].cost * c);
        }
    }
    return memo[a] = rc;
}

int main()
{
    TOTAL = 0;

    cin >> N;
    for (INT n = 0; n < (N-1); n++) {
        INT A, B;
        cin >> A;
        cin >> B;
        R[A].roots.push_back(B);
        R[B].roots.push_back(A);
    }
    for (INT n = 0; n < N; n++) {
        R[n].no = n;
        cin >> R[n].cost;
    }
    cin >> M;
    for (INT m = 0; m < M; m++) {
        INT A, B, C;
        cin >> A;
        cin >> B;
        cin >> C;
        bit = 0;
        memset(memo, 0, sizeof(memo));
        TOTAL += fn(A, B, C);
    }
    cout << TOTAL << endl;
}
0