結果
| 問題 | No.274 The Wall |
| ユーザー |
 鳩でもわかるC#
|
| 提出日時 | 2024-07-05 18:37:23 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 89 ms / 2,000 ms |
| コード長 | 5,371 bytes |
| コンパイル時間 | 8,836 ms |
| コンパイル使用メモリ | 168,668 KB |
| 実行使用メモリ | 189,708 KB |
| 最終ジャッジ日時 | 2024-07-05 18:37:39 |
| 合計ジャッジ時間 | 11,507 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 22 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (117 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;using System.Collections.Generic;using System.Linq;class TwoSAT{int N = 0;int nextId = 0;Vertex[] vertices = { };bool[] visits = { };// 連結リストと逆向きの連結リストList<int>[] list = null;List<int>[] rlist = null;class Vertex{public Vertex(int num, int id){Number = num;ID = id;}public int Number = 0;public int ID = 0;}public TwoSAT(int n){N = n;// 連結リストを生成するlist = new List<int>[n * 2];rlist = new List<int>[n * 2];for (int i = 0; i < n * 2; i++){list[i] = new List<int>();rlist[i] = new List<int>();}}public void AddConstraintV(bool xTrue, int x, bool yTrue, int y){if (!xTrue)x = TakeNot(x);if (!yTrue)y = TakeNot(y);list[TakeNot(x)].Add(y);list[TakeNot(y)].Add(x);rlist[y].Add(TakeNot(x));rlist[x].Add(TakeNot(y));}public void AddConstraintArrow(bool xTrue, int x, bool yTrue, int y){if (!xTrue)x = TakeNot(x);if (!yTrue)y = TakeNot(y);list[x].Add(y);list[y].Add(x);rlist[y].Add(x);rlist[x].Add(y);}int TakeNot(int x){if (x < N)return x + N;elsereturn x - N;}public List<bool> Solve(){visits = new bool[N * 2];vertices = new Vertex[N * 2];for (int i = 0; i < N * 2; i++)Dfs1(i, list);vertices = vertices.OrderByDescending(_ => _.ID).ToArray();int groupNumber = 0;Dictionary<int, int> dic = new Dictionary<int, int>();visits = new bool[N * 2];foreach (Vertex vertex in vertices){List<int> ret = Dfs2(vertex.Number, rlist);foreach (int i in ret)dic.Add(i, groupNumber);groupNumber++;}List<bool> values = new List<bool>();for (int i = 0; i < N; i++){if (dic[i] == dic[TakeNot(i)])return new List<bool>();if (dic[i] > dic[TakeNot(i)])values.Add(true);elsevalues.Add(false);}return values;}void Dfs1(int vNum, List<int>[] list){if (!visits[vNum]){visits[vNum] = true;dfs(vNum);}void dfs(int num){foreach (int i in list[num]){if (visits[i])continue;visits[i] = true;dfs(i);}vertices[num] = new Vertex(num, nextId++);}}List<int> Dfs2(int vNum, List<int>[] list){List<int> rets = new List<int>(); // たどり着ける頂点をリストにして返すif (!visits[vNum]) // 一度訪問した頂点は対象外{rets.Add(vNum);visits[vNum] = true;dfs(vNum);}return rets;void dfs(int num){foreach (int i in list[num]){if (visits[i])continue;visits[i] = true;dfs(i);rets.Add(i);}}}}public class Program{static void Main(){int N, M;{int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();N = vs[0];M = vs[1];}int[] L = new int[N];int[] R = new int[N];for (int i = 0; i < N; i++){int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();L[i] = vs[0];R[i] = vs[1];}TwoSAT twoSAT = new TwoSAT(N);for (int a = 0; a < N; a++){for (int b = a + 1; b < N; b++){bool b1 = (R[b] < L[a] || R[a] < L[b]);bool b2 = (M - L[b]- 1 < L[a] || R[a] < M - R[b]-1);if (b1 && !b2) // 片方だけ反転すると干渉する{twoSAT.AddConstraintArrow(false, a, false, b);twoSAT.AddConstraintArrow(true, a, true, b);//twoSAT.AddConstraintV(true, a, false, b);//twoSAT.AddConstraintV(false, a, true, b);}if (!b1 && b2) // 片方だけ反転させないと干渉する{twoSAT.AddConstraintArrow(false, a, true, b);twoSAT.AddConstraintArrow(true, a, false, b);//twoSAT.AddConstraintV(true, a, true, b);//twoSAT.AddConstraintV(false, a, false, b);}if (!b1 && !b2) // どうやっても駄目{Console.WriteLine("NO");return;}}}List<bool> rets = twoSAT.Solve();if (rets.Count == 0)Console.WriteLine("NO");elseConsole.WriteLine("YES");}}