結果

問題 No.386 貪欲な領主
コンテスト
ユーザー mban
提出日時 2016-11-04 06:04:05
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 2,768 bytes
コンパイル時間 847 ms
コンパイル使用メモリ 114,024 KB
実行使用メモリ 84,448 KB
最終ジャッジ日時 2024-11-25 02:30:03
合計ジャッジ時間 9,822 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 TLE * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 int[] bef;
    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)
    {
        List<int> SList = new List<int>(), GList = new List<int>();
        
        for(int i = s; i != 0; i = bef[i])
        {
            SList.Add(i);
        }
        for(int i = g; i != 0; i = bef[i])
        {
            GList.Add(i);
        }
        SList.Add(0);
        GList.Add(0);
        int sc = SList.Count,gc=GList.Count;
        int cvill = 0;
        for(int i=0; ; i++)
        {
            if (sc - i - 1 >= 0 && gc - i - 1 >= 0)
            {
                if (SList[sc - i - 1] == GList[gc - i - 1])
                {
                    cvill = SList[sc - 1 - 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];
        for(int i = 0; i < N; i++)
        {
            U[i] = int.Parse(Console.ReadLine());
        }
        toZero = new int[N];
        bef = new int[N];
        bool[] ed = new bool[N];
        Queue<int> q = new Queue<int>();
        q.Enqueue(0);
        toZero[0] = U[0];
        ed[0] = true;
        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;
                    bef[e] = w;
                    toZero[e] = toZero[w] + U[e];
                }
            }
        }
    }
}
0