結果

問題 No.386 貪欲な領主
ユーザー haruteruharuteru
提出日時 2016-07-05 11:28:59
言語 C++11
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,392 bytes
コンパイル時間 596 ms
コンパイル使用メモリ 63,172 KB
実行使用メモリ 23,168 KB
最終ジャッジ日時 2024-10-12 20:15:49
合計ジャッジ時間 4,349 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

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