結果
| 問題 |
No.1647 Travel in Mitaru city 2
|
| コンテスト | |
| ユーザー |
 kakel-san
|
| 提出日時 | 2024-01-23 23:35:23 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 599 ms / 2,500 ms |
| コード長 | 10,026 bytes |
| コンパイル時間 | 13,577 ms |
| コンパイル使用メモリ | 165,732 KB |
| 実行使用メモリ | 235,432 KB |
| 最終ジャッジ日時 | 2024-09-28 06:55:22 |
| 合計ジャッジ時間 | 40,562 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 48 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (131 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[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray();
static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray();
public static void Main()
{
Solve();
// Test();
}
static void Test()
{
var r = new Random();
var count = 0;
while (true)
{
var h = 10000;
var w = 10000;
var n = 10000;
var map = Make(r, h, w, n);
// 愚直解
// var s1 = All(n, t, map);
// 作成解
var s2 = Tour(h, w, n, map);
if (s2 != "-1" && !Check(s2, map))
{
WriteLine($"{h} {w} {n}");
WriteLine(string.Join("\n", map.Select(m => string.Join(" ", m))));
// WriteLine(s1);
WriteLine(s2);
WriteLine("is not good travel");
return;
}
++count;
if (count % 1000 == 0) WriteLine(count);
}
}
static int[][] Make(Random r, int h, int w, int n)
{
var set = new HashSet<int>();
var ans = new int[n][];
for (var i = 0; i < n; ++i)
{
while (true)
{
var x = r.Next(h);
var y = r.Next(w);
if (set.Add(x * w + y))
{
ans[i] = new int[] { x, y };
break;
}
}
}
return ans;
}
static bool Check(string ans, int[][] map)
{
if (ans == "-1") return true;
var c = ans.Split("\n");
var t = c[1].Split();
if (t.Length < 4) return false;
var set = new HashSet<int>();
for (var i = 0; i < t.Length; ++i)
{
var a = int.Parse(t[i]) - 1;
var b = int.Parse(t[(i + 1) % t.Length]) - 1;
if (!set.Add(a)) return false;
if (i % 2 == 0)
{
if (map[a][1] != map[b][1]) return false;
}
else
{
if (map[a][0] != map[b][0]) return false;
}
}
return true;
}
static void Solve()
{
var c = NList;
var (h, w, n) = (c[0], c[1], c[2]);
var map = NMap(n);
var ans = Tour(h, w, n, map);
// if(Check(ans, map))
// {
WriteLine(ans);
// WriteLine("OK");
// }
// else
// {
// WriteLine("!!!");
// }
}
static string Tour(int h, int w, int n, int[][] _map)
{
var map = new List<(int id, int h, int w)>(n);
for (var i = 0; i < n; ++i)
{
map.Add((i, _map[i][0] - 1, _map[i][1] - 1));
}
map.Sort((l, r) =>
{
var d = l.h.CompareTo(r.h);
if (d != 0) return d;
return l.w.CompareTo(r.w);
});
var tree = new List<int>[n];
for (var i = 0; i < tree.Length; ++i) tree[i] = new List<int>();
for (var i = 0; i + 1 < map.Count; ++i)
{
if (map[i].h == map[i + 1].h)
{
tree[map[i].id].Add(map[i + 1].id);
tree[map[i + 1].id].Add(map[i].id);
}
}
map.Sort((l, r) =>
{
var d = l.w.CompareTo(r.w);
if (d != 0) return d;
return l.h.CompareTo(r.h);
});
for (var i = 0; i + 1 < map.Count; ++i)
{
if (map[i].w == map[i + 1].w)
{
tree[map[i].id].Add(map[i + 1].id);
tree[map[i + 1].id].Add(map[i].id);
}
}
map.Sort((l, r) => l.id.CompareTo(r.id));
var visited = new bool[n];
var ntree = new List<int>[n];
for (var i = 0; i < ntree.Length; ++i) ntree[i] = new List<int>();
for (var i = 0; i < n; ++i) if (!visited[i])
{
var set = new HashSet<long>();
DFS(i, tree, set, ntree, visited);
}
// WriteLine(string.Join("\n", ntree.Select((ni, id) => $"{id}: {string.Join(" ", ni)}")));
var scc = new SCCGraph(n);
for (var i = 0; i < n; ++i) foreach (var next in ntree[i]) scc.AddEdge(i, next);
var slist = scc.SCC();
foreach (var si in slist)
{
// WriteLine($"scc {string.Join(" ", si)}");
if (si.Count >= 4)
{
var inlist = new HashSet<int>(si);
var set = new HashSet<int>();
var list = new List<int>();
var cur = si[0];
while (true)
{
if (!set.Add(cur))
{
var pos = list.IndexOf(cur);
var ans = Ans(list.Skip(pos).ToList(), map);
return $"{ans.Count}\n{string.Join(" ", ans.Select(ai => ai + 1))}";
}
list.Add(cur);
for (var i = 0; i < ntree[cur].Count; ++i)
{
if (inlist.Contains(ntree[cur][i]))
{
cur = ntree[cur][i];
break;
}
}
}
}
}
return "-1";
}
static void DFS(int cur, List<int>[] tree, HashSet<long> set, List<int>[] ntree, bool[] visited)
{
visited[cur] = true;
foreach (var next in tree[cur])
{
if (set.Add(Math.Min(cur, next) * 1000000L + Math.Max(cur, next)))
{
ntree[cur].Add(next);
DFS(next, tree, set, ntree, visited);
}
}
}
class SCCGraph
{
private int _n;
private List<(int from, int to)> edges;
public SCCGraph(int n)
{
_n = n;
edges = new List<(int, int)>();
}
public int NumVertices() { return _n; }
public void AddEdge(int from, int to) { edges.Add((from, to )); }
public (int, int[]) SCCIds()
{
var g = new CSR<int>(_n, edges);
var nowOrd = 0;
var groupNum = 0;
var visited = new List<int>(_n);
var low = new int[_n];
var ord = Enumerable.Repeat(-1, _n).ToArray();
var ids = new int[_n];
void DFS(int v)
{
low[v] = ord[v] = nowOrd++;
visited.Add(v);
for (var i = g.Start[v]; i < g.Start[v + 1]; ++i)
{
var to = g.EList[i];
if (ord[to] == -1)
{
DFS(to);
low[v] = Math.Min(low[v], low[to]);
}
else low[v] = Math.Min(low[v], ord[to]);
}
if (low[v] == ord[v])
{
while (true)
{
var u = visited.Last();
visited.RemoveAt(visited.Count - 1);
ord[u] = _n;
ids[u] = groupNum;
if (u == v) break;
}
++groupNum;
}
}
for (var i = 0; i < _n; ++i) if (ord[i] == -1) DFS(i);
for (var i = 0; i < ids.Length; ++i) ids[i] = groupNum - 1 - ids[i];
return (groupNum, ids);
}
public List<int>[] SCC()
{
var (groupNum, list) = SCCIds();
var counts = new int[groupNum];
foreach (var x in list) ++counts[x];
var groups = new List<int>[groupNum];
for (var i = 0; i < groups.Length; ++i) groups[i] = new List<int>(counts[i]);
for (var i = 0; i < _n; ++i) groups[list[i]].Add(i);
return groups;
}
}
// 有向辺のリスト
class CSR<E>
{
public int[] Start { get; private set; }
public E[] EList { get; private set; }
public CSR(int n, List<(int, E)> edges)
{
Start = new int[n + 1];
EList = new E[edges.Count];
foreach (var e in edges) ++Start[e.Item1 + 1];
for (var i = 1; i <= n; ++i) Start[i] += Start[i - 1];
var counter = (int[])Start.Clone();
foreach (var e in edges)
{
EList[counter[e.Item1]++] = e.Item2;
}
}
}
static List<int> Ans(List<int> list, List<(int id, int h, int w)> map)
{
var ans = new List<int>();
var begin = -1;
for (var i = 0; i < list.Count; ++i)
{
var pi = (list.Count - 1 + i) % list.Count;
var ni = (i + 1) % list.Count;
if (map[list[pi]].h == map[list[i]].h && map[list[i]].w == map[list[ni]].w)
{
ans.Add(list[i]);
begin = i;
break;
}
}
var tmp = (begin + 1) % list.Count;
while (tmp != begin)
{
var pi = (list.Count - 1 + tmp) % list.Count;
var ni = (tmp + 1) % list.Count;
if ((map[list[pi]].h == map[list[tmp]].h) != (map[list[tmp]].h == map[list[ni]].h)) ans.Add(list[tmp]);
tmp = (tmp + 1) % list.Count;
}
return ans;
}
}