Submission #420245
Source Code Expand
#region ZIPPER using System; using System.Collections.Generic; using System.Collections; using System.Linq; using System.Text; using sc = Scanner; using ci = CharInterpreter; //using System.Numerics; //using Geometry; //using gl = Geometry.GeometryLibrary; //using grl = GraphLibrary; class Program { static void Main(string[] args) { Solver solver = new Solver(); solver.Solve(); #if DEBUG System.Console.WriteLine("続行するには何かキーを押してください..."); System.Console.ReadKey(); #endif } } /// <summary> /// 標準入力読み取り支援,自作(某最速の人を参考) /// </summary> #endregion ZIPPER public class Solver { #region IGNORE_ME public Solver() { //こんすとらくたん きにしなくてよろしい } #endregion IGNORE_ME public int MOD = 1000000007;//10^9 + 7 public void Solve() { int n = sc.NextInt(); int q = sc.NextInt(); int[][] quary = new int[q][]; UnionFindTree uf = new UnionFindTree(n); for (int i = 0; i < q; i++) { quary[i] = sc.NextIntArray(); } for (int i = 0; i < q; i++) { if (quary[i][0] == 0) { uf.Unite(quary[i][1],quary[i][2]); } else { Console.WriteLine(uf.Same(quary[i][1], quary[i][2])?"Yes":"No"); } } #if DEBUG Console.WriteLine("t");//local check #endif } } /// <summary> /// UF木、蟻本より /// </summary> public class UnionFindTree { int[] Par; int[] Rank; /// <summary> /// nの要素数を管理するUF木 /// </summary> /// <param name="n"></param> public UnionFindTree(int n) { this.Par = new int[n]; this.Rank = new int[n]; for (int i = 0; i < n; i++) { Par[i] = i; } } /// <summary> /// 木の根を求める /// </summary> /// <param name="x"></param> /// <returns></returns> private int Find(int x) { if (Par[x] == x) return x; else { Par[x] = Find(Par[x]); return Par[x]; } } /// <summary> /// xとyの属する集合を併合 /// </summary> /// <param name="x"></param> /// <param name="y"></param> public void Unite(int x, int y) { x = Find(x); y = Find(y); if (x == y) return; if (Rank[x] < Rank[y]) { Par[x] = y; } else { Par[y] = x; if (Rank[x] == Rank[y]) Rank[x]++; } } /// <summary> /// xとyが同じ集合に属するか否か /// </summary> /// <param name="x"></param> /// <param name="y"></param> /// <returns></returns> public bool Same(int x, int y) { return Find(x) == Find(y); } } #region STANDARD_READER public static class Scanner { public static string NextString() { string tmp = ""; while (true) { int readData; string data; readData = Console.Read(); if (readData == -1) //EOF { break; } data = char.ConvertFromUtf32(readData); if (data == " " || data == "\n") { break; } tmp += data; } return tmp; } public static int NextInt() { string tmp = ""; while (true) { int readData; string data; readData = Console.Read(); if (readData == -1) //EOF { break; } data = char.ConvertFromUtf32(readData); if (data == " " || data == "\n") { break; } tmp += data; } return int.Parse(tmp); } public static long NextLong() { string tmp = ""; while (true) { int readData; string data; readData = Console.Read(); if (readData == -1) //EOF { break; } data = char.ConvertFromUtf32(readData); if (data == " " || data == "\n") { break; } tmp += data; } return long.Parse(tmp); } public static double NextDouble() { string tmp = ""; while (true) { int readData; string data; readData = Console.Read(); if (readData == -1) //EOF { break; } data = char.ConvertFromUtf32(readData); if (data == " " || data == "\n") { break; } tmp += data; } return double.Parse(tmp); } public static string[] NextStrArray() { return Console.ReadLine().Split(' '); } public static int[] NextIntArray() { string[] s = NextStrArray(); int[] a = new int[s.Length]; for (int i = 0; i < a.Length; i++) { a[i] = int.Parse(s[i]); } return a; } public static long[] NextLongArray() { string[] s = NextStrArray(); long[] a = new long[s.Length]; for (int i = 0; i < a.Length; i++) { a[i] = long.Parse(s[i]); } return a; } public static double[] NextDoubleArray() { string[] s = NextStrArray(); double[] a = new double[s.Length]; for (int i = 0; i < a.Length; i++) { a[i] = double.Parse(s[i]); } return a; } } /// <summary> /// 二次元グリッドなどの文字列で与えられたマップなどで、 /// 手軽にデータ変換を適用するためのクラス /// </summary> public static class CharInterpreter { /// <summary> /// 変換用辞書 /// </summary> private static Dictionary<char, int> MapToInt = new Dictionary<char, int>(); /// <summary> /// 変換法則を追加する /// </summary> /// <param name="c">char文字</param> /// <param name="i">対応する整数値</param> public static void AddCorrespondence(char c,int i) { MapToInt.Add(c,i); } /// <summary> /// 文字列に対して、対応付けされた /// 例外処理をしていないので注意 /// </summary> /// <returns>対応対応がなかった場合はバグる;;</returns> public static int Inquiry(char c) { int ret = 0; MapToInt.TryGetValue(c, out ret); return ret; } /// <summary> /// 指定された変換法則の元でint[,]の二次元平面を生成する /// 対応関係がない場合の例外処理をしていないので注意 /// </summary> /// <param name="field">配列の各文字列の長さが全て同じでないとうまく作動しないので注意</param> /// <returns> int[ field.length , field[0].length]型の配列 </returns> public static int[,] GenerateSquareField(string[] field) { int[,] ret = new int[field.Length, field[0].Length]; for (int i = 0; i < field.Length; i++) { for (int j = 0; j < field[0].Length; j++) { MapToInt.TryGetValue(field[i][j], out ret[i, j]); } } return ret; } } #endregion STANDARD_READER
Submission Info
Submission Time | |
---|---|
Task | B - Union Find |
User | pekoong |
Language | C# (Mono 3.2.1.0) |
Score | 100 |
Code Size | 7952 Byte |
Status | AC |
Exec Time | 1638 ms |
Memory | 26364 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01.txt |
All | 00_sample_01.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01.txt | AC | 110 ms | 8960 KB |
subtask_01_01.txt | AC | 937 ms | 20184 KB |
subtask_01_02.txt | AC | 112 ms | 9376 KB |
subtask_01_03.txt | AC | 1580 ms | 25240 KB |
subtask_01_04.txt | AC | 1368 ms | 26364 KB |
subtask_01_05.txt | AC | 183 ms | 13844 KB |
subtask_01_06.txt | AC | 180 ms | 14336 KB |
subtask_01_07.txt | AC | 1476 ms | 25116 KB |
subtask_01_08.txt | AC | 1526 ms | 26320 KB |
subtask_01_09.txt | AC | 109 ms | 8960 KB |
subtask_01_10.txt | AC | 110 ms | 9380 KB |
subtask_01_11.txt | AC | 1638 ms | 25240 KB |
subtask_01_12.txt | AC | 1633 ms | 26324 KB |
subtask_01_13.txt | AC | 1225 ms | 22368 KB |
subtask_01_14.txt | AC | 116 ms | 9624 KB |
subtask_01_15.txt | AC | 1447 ms | 25244 KB |
subtask_01_16.txt | AC | 1496 ms | 26328 KB |
subtask_01_17.txt | AC | 1065 ms | 26348 KB |
subtask_01_18.txt | AC | 1011 ms | 26332 KB |