結果

問題 No.2638 Initial fare
ユーザー parukiparuki
提出日時 2024-03-03 01:54:16
言語 JavaScript
(node v21.7.1)
結果
RE  
実行時間 -
コード長 944 bytes
コンパイル時間 289 ms
コンパイル使用メモリ 6,948 KB
実行使用メモリ 110,780 KB
最終ジャッジ日時 2024-09-29 16:38:05
合計ジャッジ時間 18,803 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 54 ms
39,296 KB
testcase_01 AC 56 ms
39,680 KB
testcase_02 AC 52 ms
39,296 KB
testcase_03 AC 54 ms
39,296 KB
testcase_04 AC 954 ms
103,524 KB
testcase_05 AC 863 ms
108,748 KB
testcase_06 AC 56 ms
39,424 KB
testcase_07 AC 819 ms
106,012 KB
testcase_08 AC 832 ms
105,928 KB
testcase_09 AC 787 ms
109,356 KB
testcase_10 AC 789 ms
110,124 KB
testcase_11 AC 55 ms
39,424 KB
testcase_12 AC 831 ms
105,452 KB
testcase_13 AC 788 ms
102,916 KB
testcase_14 AC 837 ms
109,768 KB
testcase_15 AC 833 ms
110,780 KB
testcase_16 AC 57 ms
39,552 KB
testcase_17 AC 843 ms
108,300 KB
testcase_18 AC 808 ms
106,548 KB
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 AC 55 ms
39,424 KB
testcase_23 RE -
testcase_24 RE -
testcase_25 AC 56 ms
39,424 KB
testcase_26 RE -
testcase_27 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

Main(require("fs").readFileSync("/dev/stdin", "utf8").split(/\r\n|\n|\r/));

function dfs(G, u, p) {
    // 1, 2, 3
    let sum = [0, 0, 0];
    let res = [1, 0, 0, 0];

    G[u].forEach(v => {
        if(v==p)return;
        sub = dfs(G, v, u);
        for(let i=0; ; ++i) {
            res[3] += sub[i];
            if(i==3)break;
            for(let j=0; i+j+2<=3; ++j) {
                res[3] += sub[i] * sum[j];
            }
        }
        for(let i=0; i<3; ++i) {
            sum[i] += sub[i];
        }
    });
    for(let i=0; i<2; ++i){
        res[i+1] += sum[i];
    }
    return res;
}

function Main(lines) {
    const N = parseInt(lines[0]);
    let G = Array(N);
    for(let i=0; i<N; ++i) G[i] = Array(0);
    for(let i=0; i<N-1; ++i) {
        const uv = lines[i+1].split(" ").map(Number);
        G[uv[0]-1].push(uv[1]-1);
        G[uv[1]-1].push(uv[0]-1);
    }

    const ans = dfs(G, 0, -1)[3];
    console.log(ans);
}
0