結果

問題 No.2618 除霊
ユーザー heno239heno239
提出日時 2024-02-02 17:37:47
言語 C#
(.NET 8.0.203)
結果
AC  
実行時間 1,233 ms / 2,000 ms
コード長 2,934 bytes
コンパイル時間 9,444 ms
コンパイル使用メモリ 158,704 KB
実行使用メモリ 231,972 KB
最終ジャッジ日時 2024-02-02 17:38:45
合計ジャッジ時間 53,673 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 75 ms
32,804 KB
testcase_01 AC 88 ms
32,804 KB
testcase_02 AC 76 ms
32,804 KB
testcase_03 AC 76 ms
32,804 KB
testcase_04 AC 77 ms
32,804 KB
testcase_05 AC 76 ms
32,804 KB
testcase_06 AC 1,165 ms
79,988 KB
testcase_07 AC 1,134 ms
79,984 KB
testcase_08 AC 1,185 ms
81,812 KB
testcase_09 AC 1,189 ms
83,436 KB
testcase_10 AC 1,216 ms
85,008 KB
testcase_11 AC 1,121 ms
79,628 KB
testcase_12 AC 1,213 ms
81,828 KB
testcase_13 AC 1,021 ms
79,044 KB
testcase_14 AC 1,109 ms
85,684 KB
testcase_15 AC 1,001 ms
79,152 KB
testcase_16 AC 1,005 ms
79,116 KB
testcase_17 AC 1,106 ms
82,764 KB
testcase_18 AC 1,085 ms
84,468 KB
testcase_19 AC 1,040 ms
79,164 KB
testcase_20 AC 1,024 ms
79,164 KB
testcase_21 AC 1,050 ms
82,416 KB
testcase_22 AC 1,114 ms
85,972 KB
testcase_23 AC 1,061 ms
79,168 KB
testcase_24 AC 1,035 ms
79,136 KB
testcase_25 AC 1,120 ms
82,604 KB
testcase_26 AC 1,059 ms
84,232 KB
testcase_27 AC 1,050 ms
79,128 KB
testcase_28 AC 1,026 ms
79,312 KB
testcase_29 AC 1,119 ms
82,748 KB
testcase_30 AC 1,128 ms
85,664 KB
testcase_31 AC 1,194 ms
81,832 KB
testcase_32 AC 1,119 ms
78,508 KB
testcase_33 AC 1,166 ms
79,144 KB
testcase_34 AC 1,127 ms
79,720 KB
testcase_35 AC 1,118 ms
80,384 KB
testcase_36 AC 1,169 ms
81,320 KB
testcase_37 AC 1,190 ms
81,660 KB
testcase_38 AC 1,206 ms
82,472 KB
testcase_39 AC 1,233 ms
83,500 KB
testcase_40 AC 1,190 ms
83,976 KB
testcase_41 AC 1,201 ms
84,648 KB
testcase_42 AC 1,193 ms
231,972 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (92 ms)。
MSBuild のバージョン 17.7.3+8ec440e68 (.NET)
  main -> /home/judge/data/code/bin/Release/net7.0/main.dll
  main -> /home/judge/data/code/bin/Release/net7.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