結果

問題 No.812 Change of Class
ユーザー claw88claw88
提出日時 2019-04-12 22:04:38
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 886 ms / 4,000 ms
コード長 8,300 bytes
コンパイル時間 5,033 ms
コンパイル使用メモリ 111,148 KB
実行使用メモリ 55,428 KB
最終ジャッジ日時 2023-09-03 12:29:25
合計ジャッジ時間 25,242 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 336 ms
42,004 KB
testcase_01 AC 107 ms
24,996 KB
testcase_02 AC 209 ms
34,956 KB
testcase_03 AC 380 ms
46,496 KB
testcase_04 AC 353 ms
46,484 KB
testcase_05 AC 886 ms
46,252 KB
testcase_06 AC 591 ms
45,712 KB
testcase_07 AC 87 ms
28,252 KB
testcase_08 AC 76 ms
23,148 KB
testcase_09 AC 775 ms
46,608 KB
testcase_10 AC 822 ms
48,532 KB
testcase_11 AC 146 ms
45,184 KB
testcase_12 AC 562 ms
46,776 KB
testcase_13 AC 69 ms
23,828 KB
testcase_14 AC 69 ms
24,012 KB
testcase_15 AC 540 ms
46,092 KB
testcase_16 AC 88 ms
22,140 KB
testcase_17 AC 471 ms
43,696 KB
testcase_18 AC 319 ms
40,356 KB
testcase_19 AC 444 ms
43,448 KB
testcase_20 AC 886 ms
46,500 KB
testcase_21 AC 353 ms
39,420 KB
testcase_22 AC 168 ms
33,476 KB
testcase_23 AC 84 ms
24,088 KB
testcase_24 AC 93 ms
22,656 KB
testcase_25 AC 147 ms
32,580 KB
testcase_26 AC 694 ms
46,448 KB
testcase_27 AC 571 ms
43,488 KB
testcase_28 AC 371 ms
43,260 KB
testcase_29 AC 124 ms
25,656 KB
testcase_30 AC 471 ms
45,776 KB
testcase_31 AC 381 ms
43,628 KB
testcase_32 AC 197 ms
35,304 KB
testcase_33 AC 541 ms
44,088 KB
testcase_34 AC 90 ms
22,396 KB
testcase_35 AC 139 ms
32,064 KB
testcase_36 AC 93 ms
24,384 KB
testcase_37 AC 251 ms
35,336 KB
testcase_38 AC 93 ms
29,136 KB
testcase_39 AC 258 ms
35,312 KB
testcase_40 AC 109 ms
24,956 KB
testcase_41 AC 88 ms
28,448 KB
testcase_42 AC 587 ms
41,708 KB
testcase_43 AC 161 ms
37,628 KB
testcase_44 AC 370 ms
35,416 KB
testcase_45 AC 93 ms
24,308 KB
testcase_46 AC 154 ms
39,424 KB
testcase_47 AC 353 ms
37,460 KB
testcase_48 AC 421 ms
41,028 KB
testcase_49 AC 141 ms
29,264 KB
testcase_50 AC 72 ms
21,932 KB
testcase_51 AC 146 ms
35,116 KB
testcase_52 AC 252 ms
39,740 KB
testcase_53 AC 113 ms
24,780 KB
testcase_54 AC 106 ms
24,644 KB
testcase_55 AC 285 ms
49,168 KB
testcase_56 AC 334 ms
55,384 KB
testcase_57 AC 347 ms
53,560 KB
testcase_58 AC 214 ms
47,696 KB
testcase_59 AC 385 ms
55,428 KB
testcase_60 AC 69 ms
21,900 KB
testcase_61 AC 69 ms
19,868 KB
testcase_62 AC 70 ms
22,012 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.IO;
using SB = System.Text.StringBuilder;
//using System.Threading.Tasks;
//using System.Text.RegularExpressions;
//using System.Globalization;
//using System.Diagnostics;
using static System.Console;
using System.Numerics;
using static System.Math;
using pair = Pair<int, int>;

class Program
{
    static void Main()
    {
        SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    readonly Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑
    readonly int mod = 1000000007;
    readonly int dom = 998244353;
    bool chmax<T>(ref T a, T b) where T : IComparable<T> { if (a.CompareTo(b) < 0) { a = b; return true; } return false; }
    bool chmin<T>(ref T a, T b) where T : IComparable<T> { if (b.CompareTo(a) < 0) { a = b; return true; } return false; }

    List<int>[] G;
    int[] C;


    void solve()
    {
        int N = cin.nextint;
        int M = cin.nextint;
        G = Enumerable.Range(0, N).Select(i => new List<int>()).ToArray();
        for (int i = 0; i < M; i++)
        {
            int p = cin.nextint - 1;
            int q = cin.nextint - 1;
            G[p].Add(q);
            G[q].Add(p);
        }

        var L = new List<int>();
        L.Add(1);
        while (L.Last() <= N)
        {
            L.Add(L.Last() << 1);
        }


        int R = cin.nextint;
        for (int i = 0; i < R; i++)
        {
            C = new int[N];
            for (int j = 0; j < N; j++)
            {
                C[j] = -1;
            }
            int a = cin.nextint - 1;
            C[a] = 0;

            var Q = new Queue<int>();
            Q.Enqueue(a);
            while (Q.Count > 0)
            {
                int u = Q.Dequeue();
                foreach (var v in G[u])
                {
                    if (C[v] == -1)
                    {
                        C[v] = C[u] + 1;
                        Q.Enqueue(v);
                    }
                }
            }
            
            int sum = 0;
            int max = 1;
            for (int j = 0; j < N; j++)
            {
                if (C[j] > 0)
                {
                    sum++;
                }
                chmax(ref max, C[j]);
            }

            WriteLine($"{sum} {L.lower_bound(max)}");
        }


    }

}


class PotentialDisjointSet
{
    readonly int[] par;
    readonly byte[] rank;
    readonly long[] diff_weight;
    /// <summary>
    /// 0 から <paramref name="N"/>-1 までの番号がついた <paramref name="N"/> 個の要素からなる集合を作成します．
    /// </summary>
    /// <param name="N">要素数</param>
    /// <remarks>このコンストラクタは O(N) で実行されます．</remarks>
    public PotentialDisjointSet(int N)
    {
        par = new int[N];
        rank = new byte[N];
        diff_weight = new long[N];
        for (int i = 0; i < N; i++) par[i] = -1;
    }
    /// <summary>
    /// 指定した要素が属する集合の代表値を取得します．
    /// </summary>
    /// <param name="id">調べたい要素の 0-indexed での番号</param>
    /// <returns>指定した要素が属する集合の代表値</returns>
    /// <remarks>最悪計算量 O(α(N)) で実行されます．</remarks>
    public int this[int id]
    {
        get
        {
            if (par[id] < 0) return id;
            int r = this[par[id]];
            diff_weight[id] += diff_weight[par[id]];
            return par[id] = r;
        }
    }
    /// <summary>
    /// 指定した 2 つの要素が属する集合同士を 1 つに統合することを試みます．weight(y) = weight(x) + w です．
    /// </summary>
    /// <param name="x">最初の要素の 0-indexed での番号</param>
    /// <param name="y">2 つ目の要素の 0-indexed での番号</param>
    /// <param name="w">weight(y) = weight(x) + w となるポテンシャル</param>
    /// <returns>統合に成功したならば true，そうでなければ false．</returns>
    /// <remarks>最悪計算量 O(α(N)) で実行されます．</remarks>
    public bool Unite(int x, int y, long w)
    {
        w += Weight(x); w -= Weight(y);
        x = this[x]; y = this[y];
        if (x == y) return false;
        if (rank[x] < rank[y]) { var tmp = x; x = y; y = tmp; w = -w; }
        par[x] += par[y];
        par[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
        diff_weight[y] = w;
        return true;
    }
    /// <summary>
    /// 指定した要素が属する集合のサイズを取得します．
    /// </summary>
    /// <param name="x">指定する要素の 0-indexed での番号</param>
    /// <returns>集合のサイズ</returns>
    /// <remarks>最悪計算量 O(α(N)) で実行されます．</remarks>
    public int Size(int x) => -par[this[x]];

    /// <summary>
    /// 指定した 2 つの要素が属する集合が同じかどうかを判定する．計算量 O(α(N))．
    /// </summary>
    /// <param name="x">最初の要素の 0-indexed での番号</param>
    /// <param name="y">2 つ目の要素の 0-indexed での番号</param>
    /// <returns>同じならば true，そうでなければ false．</returns>
    /// <remarks>最悪計算量 O(α(N)) で実行されます．</remarks>
    public bool Same(int x, int y) => this[x] == this[y];

    long Weight(int x)
    {
        var tmp = this[x];
        return diff_weight[x];
    }
    /// <summary>
    /// 指定した 2 つの要素のポテンシャルの差．Weight(y) - Weight(x)．計算量 O(α(N))．
    /// </summary>
    /// <param name="x">最初の要素の 0-indexed での番号</param>
    /// <param name="y">2 つ目の要素の 0-indexed での番号</param>
    /// <returns>ポテンシャルの差</returns>
    /// <remarks>最悪計算量 O(α(N)) で実行されます．</remarks>
    public long Diff(int x, int y) => Weight(y) - Weight(x);
}

static class Ex
{
    public static void join<T>(this IEnumerable<T> values, string sep = " ") => WriteLine(string.Join(sep, values));
    public static string concat<T>(this IEnumerable<T> values) => string.Concat(values);
    public static string reverse(this string s) { var t = s.ToCharArray(); Array.Reverse(t); return t.concat(); }

    public static int lower_bound<T>(this IList<T> arr, T val) where T : IComparable<T>
    {
        int low = 0, high = arr.Count;
        int mid;
        while (low < high)
        {
            mid = ((high - low) >> 1) + low;
            if (arr[mid].CompareTo(val) < 0) low = mid + 1;
            else high = mid;
        }
        return low;
    }
    public static int upper_bound<T>(this IList<T> arr, T val) where T : IComparable<T>
    {
        int low = 0, high = arr.Count;
        int mid;
        while (low < high)
        {
            mid = ((high - low) >> 1) + low;
            if (arr[mid].CompareTo(val) <= 0) low = mid + 1;
            else high = mid;
        }
        return low;
    }
}

class Pair<T, U> : IComparable<Pair<T, U>> where T : IComparable<T> where U : IComparable<U>
{
    public T f; public U s;
    public Pair(T f, U s) { this.f = f; this.s = s; }
    public int CompareTo(Pair<T, U> a) => f.CompareTo(a.f) != 0 ? f.CompareTo(a.f) : s.CompareTo(a.s);
    public override string ToString() => $"{f} {s}";
}

class Scanner
{
    string[] s; int i;
    readonly char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan => ReadLine().Split();
    public int[] scanint => Array.ConvertAll(scan, int.Parse);
    public long[] scanlong => Array.ConvertAll(scan, long.Parse);
    public double[] scandouble => Array.ConvertAll(scan, double.Parse);
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint => int.Parse(next);
    public long nextlong => long.Parse(next);
    public double nextdouble => double.Parse(next);
}
0