結果
問題 | No.274 The Wall |
ユーザー | eitaho |
提出日時 | 2016-06-08 17:34:26 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,621 bytes |
コンパイル時間 | 1,172 ms |
コンパイル使用メモリ | 119,536 KB |
実行使用メモリ | 26,964 KB |
最終ジャッジ日時 | 2024-10-09 03:13:15 |
合計ジャッジ時間 | 3,252 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 26 ms
18,560 KB |
testcase_01 | AC | 26 ms
18,688 KB |
testcase_02 | AC | 27 ms
18,432 KB |
testcase_03 | AC | 28 ms
18,816 KB |
testcase_04 | AC | 28 ms
18,688 KB |
testcase_05 | AC | 28 ms
18,816 KB |
testcase_06 | AC | 28 ms
18,688 KB |
testcase_07 | AC | 28 ms
18,560 KB |
testcase_08 | AC | 28 ms
18,432 KB |
testcase_09 | AC | 27 ms
18,432 KB |
testcase_10 | AC | 28 ms
18,688 KB |
testcase_11 | AC | 28 ms
18,816 KB |
testcase_12 | AC | 48 ms
18,944 KB |
testcase_13 | AC | 29 ms
18,816 KB |
testcase_14 | AC | 34 ms
18,944 KB |
testcase_15 | AC | 42 ms
18,816 KB |
testcase_16 | AC | 28 ms
18,816 KB |
testcase_17 | AC | 29 ms
18,944 KB |
testcase_18 | AC | 27 ms
18,816 KB |
testcase_19 | AC | 54 ms
18,944 KB |
testcase_20 | AC | 59 ms
19,072 KB |
testcase_21 | AC | 59 ms
19,072 KB |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | AC | 61 ms
18,944 KB |
testcase_25 | AC | 62 ms
19,200 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.Linq;using System.Text;using System.Text.RegularExpressions;using System.Collections.Generic;using System.Diagnostics;using System.Numerics;using Enu = System.Linq.Enumerable;public class Program{public void Solve(){int N = Reader.Int(), W = Reader.Int();int[] L = new int[N], R = new int[N];for (int i = 0; i < N; i++) { L[i] = Reader.Int(); R[i] = Reader.Int() + 1; }var uf = new UnionFind(N * 2);for (int a = 0; a < N; a++)for (int b = a + 1; b < N; b++){bool intersect1 = Intersect(L[a], R[a], L[b], R[b]);bool intersect2 = Intersect(W - R[a], W - L[a], L[b], R[b]);if (intersect1 && intersect2) { Console.WriteLine("NO"); return; }if (intersect1){uf.Unite(a, N + b);uf.Unite(N + a, b);}if (intersect2){uf.Unite(a, b);uf.Unite(N + a, N + b);}}bool ok = Enu.Range(0, N * 2).All(a => uf.NumElements(a) <= N);Console.WriteLine(ok ? "YES" : "NO");Console.ReadLine();}bool Intersect(int L1, int R1, int L2, int R2){return !(R1 <= L2 || L1 >= R2);}class UnionFind{private int[] parent;private int[] rank;private int[] numElements;public UnionFind(int N){parent = new int[N];rank = new int[N];numElements = new int[N];for (int i = 0; i < N; i++){parent[i] = i;numElements[i] = 1;}}public int Root(int x){if (parent[x] == x) return x;return parent[x] = Root(parent[x]);}public bool Same(int x, int y){return Root(x) == Root(y);}public int NumElements(int x){return numElements[Root(x)];}public bool Unite(int x, int y){x = Root(x); y = Root(y);if (x == y) return false;if (rank[x] > rank[y]) { var t = x; x = y; y = t; }if (rank[x] == rank[y]) rank[y]++;parent[x] = y;numElements[y] += numElements[x];return true;}public Dictionary<int, List<int>> Components(){var dic = new Dictionary<int, List<int>>();for (int i = 0; i < parent.Length; i++){int root = Root(i);if (!dic.ContainsKey(root)) dic[root] = new List<int>();dic[root].Add(i);}return dic;}}}class Entry { static void Main() { new Program().Solve(); } }class Reader{static TextReader reader = Console.In;static readonly char[] separator = { ' ' };static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;static string[] A = new string[0];static int i;static void Init() { A = new string[0]; }public static void Set(TextReader r) { reader = r; Init(); }public static void Set(string file) { reader = new StreamReader(file); Init(); }public static bool HasNext() { return CheckNext(); }public static string String() { return Next(); }public static int Int() { return int.Parse(Next()); }public static long Long() { return long.Parse(Next()); }public static double Double() { return double.Parse(Next()); }public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }public static int[] IntArray(int N) { return Range(N, Int); }public static int[][] IntTable(int H) { return Range(H, IntLine); }public static string[] StringArray(int N) { return Range(N, Next); }public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); }public static string Line() { return reader.ReadLine().Trim(); }static T[] Range<T>(int N, Func<T> f) { return Enu.Range(0, N).Select(i => f()).ToArray(); }static string[] Split(string s) { return s.Split(separator, op); }static string Next() { CheckNext(); return A[i++]; }static bool CheckNext(){if (i < A.Length) return true;string line = reader.ReadLine();if (line == null) return false;if (line == "") return CheckNext();A = Split(line);i = 0;return true;}}