結果
問題 | No.2696 Sign Creation |
ユーザー |
|
提出日時 | 2024-03-22 23:42:32 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 1,697 ms / 2,500 ms |
コード長 | 4,395 bytes |
コンパイル時間 | 8,544 ms |
コンパイル使用メモリ | 167,480 KB |
実行使用メモリ | 191,740 KB |
最終ジャッジ日時 | 2024-12-20 12:35:40 |
合計ジャッジ時間 | 18,131 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (105 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 static System.Console;using System.Linq;using System.Collections.Generic;class Program{static int NN => int.Parse(ReadLine());static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();public static void Main(){Solve();}static void Solve(){var c = NList;var (h, w, n, d) = (c[0], c[1], c[2], c[3]);var map = NArr(n);WriteLine(Stars(h, w, n, d, map));}static string Stars(int h, int w, int n, int d, int[][] map){var dic = new Dictionary<long, int>();for (var i = 0; i < n; ++i){var k = Key(map[i][0], map[i][1]);dic[k] = i;}var uf = new UnionFindTree(n);for (var i = 0; i < n; ++i){var ix = map[i][0];var iy = map[i][1];foreach (var pos in Search(ix, iy, h, w, d)){var pk = Key(pos.x, pos.y);if (dic.ContainsKey(pk)) uf.Unite(i, dic[pk]);}}var newstar = new Dictionary<long, Data>();for (var i = 0; i < n; ++i){var ix = map[i][0];var iy = map[i][1];foreach (var pos in Search(ix, iy, h, w, d)){var k = Key(pos.x, pos.y);if (dic.ContainsKey(k)) continue;if (!newstar.ContainsKey(k)) newstar[k] = new Data();if (uf.GetSize(i) == 1) newstar[k].Singles.Add(i);else newstar[k].Signs.Add(uf.GetRoot(i));}}var sum = 0;for (var i = 0; i < n; ++i) if (uf.GetRoot(i) == i && uf.GetSize(i) > 1) ++sum;var min = int.MaxValue;var max = 0;foreach (var s in newstar){var sub = sum;if (s.Value.Signs.Count > 0){sub -= s.Value.Signs.Count - 1;}else if (s.Value.Singles.Count > 0){++sub;}min = Math.Min(min, sub);max = Math.Max(max, sub);}var flg = false;for (var i = 1; i <= h; ++i){for (var j = 1; j <= w; ++j){var k = Key(i, j);if (!dic.ContainsKey(k) && !newstar.ContainsKey(k)){min = Math.Min(min, sum);max = Math.Max(max, sum);flg = true;break;}}if (flg) break;}return $"{min} {max}";}class Data{public HashSet<int> Singles = new HashSet<int>();public HashSet<int> Signs = new HashSet<int>();}static IEnumerable<(int x, int y)> Search(int sx, int sy, int h, int w, int d){for (var i = Math.Max(1, sx - d); i <= Math.Min(h, sx + d); ++i){var di = Math.Abs(sx - i);for (var j = Math.Max(1, sy - d + di); j <= Math.Min(w, sy + d - di); ++j){if (i != sx || j != sy) yield return (i, j);}}}static long Key(int x, int y){return x * 1_000_000L + y;}class UnionFindTree{int[] roots;public UnionFindTree(int size){roots = new int[size];for (var i = 0; i < size; ++i) roots[i] = -1;}public int GetRoot(int a){if (roots[a] < 0) return a;return roots[a] = GetRoot(roots[a]);}public bool IsSameTree(int a, int b){return GetRoot(a) == GetRoot(b);}public bool Unite(int a, int b){var x = GetRoot(a);var y = GetRoot(b);if (x == y) return false;if (-roots[x] < -roots[y]) { var tmp = x; x = y; y = tmp; }roots[x] += roots[y];roots[y] = x;return true;}public int GetSize(int a){return -roots[GetRoot(a)];}}}