結果
問題 | No.556 仁義なきサルたち |
ユーザー | AreTrash |
提出日時 | 2019-01-24 00:27:18 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 65 ms / 2,000 ms |
コード長 | 3,202 bytes |
コンパイル時間 | 2,373 ms |
コンパイル使用メモリ | 106,512 KB |
実行使用メモリ | 28,896 KB |
最終ジャッジ日時 | 2023-10-14 09:33:39 |
合計ジャッジ時間 | 5,016 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 53 ms
20,604 KB |
testcase_01 | AC | 50 ms
20,728 KB |
testcase_02 | AC | 48 ms
20,740 KB |
testcase_03 | AC | 49 ms
22,748 KB |
testcase_04 | AC | 50 ms
22,744 KB |
testcase_05 | AC | 49 ms
22,620 KB |
testcase_06 | AC | 48 ms
20,704 KB |
testcase_07 | AC | 51 ms
22,748 KB |
testcase_08 | AC | 51 ms
20,712 KB |
testcase_09 | AC | 49 ms
18,664 KB |
testcase_10 | AC | 49 ms
20,724 KB |
testcase_11 | AC | 50 ms
22,824 KB |
testcase_12 | AC | 49 ms
20,760 KB |
testcase_13 | AC | 50 ms
20,656 KB |
testcase_14 | AC | 56 ms
22,808 KB |
testcase_15 | AC | 53 ms
20,756 KB |
testcase_16 | AC | 52 ms
20,636 KB |
testcase_17 | AC | 55 ms
24,680 KB |
testcase_18 | AC | 65 ms
24,828 KB |
testcase_19 | AC | 57 ms
24,688 KB |
testcase_20 | AC | 57 ms
24,784 KB |
testcase_21 | AC | 60 ms
28,896 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.IO; using System.Collections.Generic; namespace No556 { public class Program { void Solve(StreamScanner ss, StreamWriter sw) { //--------------------------------- var N = ss.Next(int.Parse); var M = ss.Next(int.Parse); var uf = new UnionFind(N + 1); for (var i = 0; i < M; i++) { var A = ss.Next(int.Parse); var B = ss.Next(int.Parse); if (uf.Root(A) > uf.Root(B)) MathX.Swap(ref A, ref B); uf.Unite(A, B); } for (var i = 1; i <= N; i++) { sw.WriteLine(uf.Root(i)); } //--------------------------------- } static void Main() { var ss = new StreamScanner(new StreamReader(Console.OpenStandardInput())); var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false}; new Program().Solve(ss, sw); sw.Flush(); } } public static partial class MathX { public static void Swap<T>(ref T left, ref T right) { var tmp = left; left = right; right = tmp; } } public class UnionFind { readonly int[] p; public UnionFind(int n) { p = new int[n]; for (var i = 0; i < n; i++) p[i] = -1; } public int Root(int x) { return p[x] < 0 ? x : (p[x] = Root(p[x])); } public bool IsSameSet(int x, int y) { return Root(x) == Root(y); } public bool Unite(int x, int y) { x = Root(x); y = Root(y); if (x == y) return false; if (p[x] > p[y]) { var t = x; x = y; y = t; } p[x] += p[y]; p[y] = x; return true; } public int Size(int x) { return -p[Root(x)]; } } public class StreamScanner { static readonly char[] Sep = {' '}; readonly Queue<string> buffer = new Queue<string>(); readonly TextReader textReader; public StreamScanner(TextReader textReader) { this.textReader = textReader; } public T Next<T>(Func<string, T> parser) { if (buffer.Count != 0) return parser(buffer.Dequeue()); var nextStrings = textReader.ReadLine().Split(Sep, StringSplitOptions.RemoveEmptyEntries); foreach (var nextString in nextStrings) buffer.Enqueue(nextString); return Next(parser); } public T[] Next<T>(Func<string, T> parser, int x) { var ret = new T[x]; for (var i = 0; i < x; ++i) ret[i] = Next(parser); return ret; } public T[][] Next<T>(Func<string, T> parser, int x, int y) { var ret = new T[y][]; for (var i = 0; i < y; ++i) ret[i] = Next(parser, x); return ret; } } }