結果

問題 No.2618 除霊
ユーザー heno239heno239
提出日時 2024-02-02 17:37:47
言語 C#
(.NET 8.0.203)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 55 ms
30,548 KB
testcase_01 AC 58 ms
30,336 KB
testcase_02 AC 56 ms
30,428 KB
testcase_03 AC 56 ms
30,336 KB
testcase_04 AC 57 ms
30,588 KB
testcase_05 AC 55 ms
30,720 KB
testcase_06 AC 1,077 ms
79,172 KB
testcase_07 AC 1,060 ms
79,284 KB
testcase_08 AC 1,115 ms
82,920 KB
testcase_09 AC 1,076 ms
85,052 KB
testcase_10 AC 1,152 ms
88,356 KB
testcase_11 AC 1,034 ms
77,912 KB
testcase_12 AC 1,111 ms
82,928 KB
testcase_13 AC 942 ms
76,832 KB
testcase_14 AC 1,029 ms
89,464 KB
testcase_15 AC 929 ms
76,936 KB
testcase_16 AC 930 ms
76,652 KB
testcase_17 AC 996 ms
82,596 KB
testcase_18 AC 998 ms
88,816 KB
testcase_19 AC 961 ms
76,932 KB
testcase_20 AC 948 ms
76,832 KB
testcase_21 AC 993 ms
81,924 KB
testcase_22 AC 1,022 ms
91,732 KB
testcase_23 AC 992 ms
77,084 KB
testcase_24 AC 1,003 ms
76,904 KB
testcase_25 AC 1,047 ms
82,568 KB
testcase_26 AC 1,014 ms
88,808 KB
testcase_27 AC 963 ms
77,032 KB
testcase_28 AC 966 ms
77,240 KB
testcase_29 AC 1,034 ms
82,584 KB
testcase_30 AC 1,078 ms
91,908 KB
testcase_31 AC 1,096 ms
82,808 KB
testcase_32 AC 1,070 ms
76,280 KB
testcase_33 AC 1,106 ms
77,172 KB
testcase_34 AC 1,084 ms
78,264 KB
testcase_35 AC 1,164 ms
79,788 KB
testcase_36 AC 1,122 ms
81,012 KB
testcase_37 AC 1,086 ms
82,768 KB
testcase_38 AC 1,133 ms
83,428 KB
testcase_39 AC 1,123 ms
84,856 KB
testcase_40 AC 1,108 ms
85,716 KB
testcase_41 AC 1,184 ms
88,008 KB
testcase_42 AC 1,141 ms
247,232 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /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