結果

問題 No.2618 除霊
ユーザー heno239
提出日時 2024-02-02 17:37:47
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 1,184 ms / 2,000 ms
コード長 2,934 bytes
コンパイル時間 9,207 ms
コンパイル使用メモリ 168,172 KB
実行使用メモリ 247,232 KB
最終ジャッジ日時 2024-09-28 10:37:57
合計ジャッジ時間 50,535 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 43
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (105 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

// See https://aka.ms/new-console-template for more information
using System.Collections;
using System.Runtime.InteropServices;

internal class Program
{
    public static void Main(string[] args)
    {
        
        int n = int.Parse(Console.ReadLine());
        List<List<int>> G = new List<List<int>>(n);
        for(int i=0;i<n;i++)G.Add(new List<int>());
        for (int i = 0; i < n-1; i++)
        {
            var line = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int a = line[0], b = line[1];
            a--;
            b--;
            G[a].Add(b);
            G[b].Add(a);
            //Console.WriteLine("first edge {0} and {1}",a,b);
        }

        List<int> cnt = new List<int>(n);
        for (int i = 0; i < n; i++) cnt.Add(0);
        List<int> mk = new List<int>(n);
        for (int i = 0; i < n; i++) mk.Add(-1);
        int m = int.Parse(Console.ReadLine());
        var v =Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

        List<bool> exi = new List<bool>(n);
        for(int i=0;i<n;i++)exi.Add(false);
        for (int i = 0; i < m; i++)
        {
            v[i]--;
            exi[v[i]] = true;
            for (int j = 0; j < G[v[i]].Count; j++)
            {
                int to = G[v[i]][j];
                cnt[to]++;
                mk[to] = v[i];
                //Console.WriteLine("edge {0} to {1}",i,to);
            }
        }

        List<int> ps = mkar(n, 0);
        for (int i = 0; i < n; i++)
        {
            if (cnt[i] == 1&&!exi[i])
            {
                //Console.WriteLine("bad {0}",i);
                //Console.WriteLine(cnt[i]);
                ps[mk[i]]++;
            }
        }
        int preans = 0;
        for(int i=0;i<n;i++)
            if (cnt[i]>0||exi[i])
                preans++;
        //Console.WriteLine((preans));
        for (int i = 0; i < n; i++)
        {
            //Console.WriteLine("adj {0}",ps[i]);
        }
        for (int i = 0; i < n; i++)
        {
            int ans = preans;
            //distance 2
            for (int j = 0; j < G[i].Count(); j++)
            {
                int to = G[i][j];
                ans -= ps[to];
            }
            //Console.WriteLine("hello {0}", ans);
            if (cnt[i] == 1&&!exi[i]) ans++;
            //distance 0
            if (exi[i]||cnt[i]>0) ans--;
            //Console.WriteLine("hello {0}", ans);
            //Console.WriteLine(exi[i]);
            //distance 1
            for (int j = 0; j < G[i].Count(); j++)
            {
                int to = G[i][j];
                if (cnt[to] == 1 && mk[to] == i) ans--;
                else if (cnt[to] == 0 && exi[to]) ans--;
            }
            Console.WriteLine(ans);
        }
    }

    public static List<int> mkar(int n, int val)
    {
        List<int> res = new List<int>(n);
        for(int i=0;i<n;i++)res.Add(val);
        return res;
    }
}
0