結果

問題 No.386 貪欲な領主
ユーザー mbanmban
提出日時 2016-11-04 06:14:21
言語 C#(csc)
(csc 3.9.0)
結果
MLE  
実行時間 -
コード長 2,532 bytes
コンパイル時間 1,227 ms
コンパイル使用メモリ 116,000 KB
実行使用メモリ 824,480 KB
最終ジャッジ日時 2024-11-25 02:30:11
合計ジャッジ時間 7,452 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
25,004 KB
testcase_01 AC 30 ms
25,144 KB
testcase_02 AC 30 ms
25,144 KB
testcase_03 AC 29 ms
23,220 KB
testcase_04 MLE -
testcase_05 AC 585 ms
62,984 KB
testcase_06 AC 556 ms
63,364 KB
testcase_07 AC 34 ms
25,144 KB
testcase_08 AC 94 ms
32,800 KB
testcase_09 AC 36 ms
25,268 KB
testcase_10 AC 29 ms
25,272 KB
testcase_11 AC 30 ms
27,344 KB
testcase_12 AC 33 ms
23,224 KB
testcase_13 AC 46 ms
31,148 KB
testcase_14 AC 555 ms
63,476 KB
testcase_15 MLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Magatro
{
    static int N, M;
    static List<int>[] Root;
    static int[] U;
    static int[] toZero;
    static List<int>[] R;
    static void Main()
    {
        Read();
        int cnt = 0;
        int m = int.Parse(Console.ReadLine());
        for(int i = 0; i < m; i++)
        {
            int[] abc = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            int c = calc(abc[0], abc[1]) * abc[2];
          //  Console.WriteLine(c);
            cnt += c;
        }
        Console.WriteLine(cnt);
    }
    static int calc(int s, int g)
    {

        int sc = R[s].Count, gc = R[g].Count ;
        int cvill = 0;
        for(int i=0; ; i++)
        {
            if (i<sc && i<gc)
            {
                if (R[s][i]==R[g][i])
                {
                    cvill = R[s][i];
                }
                else
                {
                    break;
                }
            }
            else
            {
                break;
            }
        }
        return toZero[s] + toZero[g] - toZero[cvill] - toZero[cvill]+U[cvill];
    }
    static void Read()
    {
        N = int.Parse(Console.ReadLine());
        Root = new List<int>[N];
     
        for (int i = 0; i < N; i++)
        {
            Root[i] = new List<int>();
        }
        for (int i = 0; i < N - 1; i++)
        {
            string[] s = Console.ReadLine().Split(' ');
            int a = int.Parse(s[0]);
            int b = int.Parse(s[1]);
            Root[a].Add(b);
            Root[b].Add(a);
        }
        U = new int[N];
        R = new List<int>[N];
        for (int i = 0; i < N; i++)
        {
            R[i] = new List<int>();
            U[i] = int.Parse(Console.ReadLine());
        }
    
        toZero = new int[N];
        bool[] ed = new bool[N];
        Queue<int> q = new Queue<int>();
        q.Enqueue(0);
        toZero[0] = U[0];
        ed[0] = true;
        R[0].Add(0);
        while (q.Count > 0)
        {
            int w = q.Dequeue();
            for(int i = 0; i < Root[w].Count; i++)
            {
                int e = Root[w][i];
                if (!ed[e])
                {
                    q.Enqueue(e);
                    ed[e] = true;
                    toZero[e] = toZero[w] + U[e];
                    R[e] = R[w].ToList();
                    R[e].Add(e);
                }
            }
        }
    }
}
0