結果
問題 | No.812 Change of Class |
ユーザー |
|
提出日時 | 2019-04-12 22:04:38 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 510 ms / 4,000 ms |
コード長 | 8,300 bytes |
コンパイル時間 | 942 ms |
コンパイル使用メモリ | 118,776 KB |
実行使用メモリ | 59,524 KB |
最終ジャッジ日時 | 2024-06-12 18:23:57 |
合計ジャッジ時間 | 14,186 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 60 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
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);}