結果
| 問題 |
No.1078 I love Matrix Construction
|
| ユーザー |
 kakel-san
|
| 提出日時 | 2025-10-12 15:06:12 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 188 ms / 2,000 ms |
| コード長 | 6,135 bytes |
| コンパイル時間 | 8,052 ms |
| コンパイル使用メモリ | 170,160 KB |
| 実行使用メモリ | 189,324 KB |
| 最終ジャッジ日時 | 2025-10-12 15:06:26 |
| 合計ジャッジ時間 | 12,702 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 22 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (106 ミリ秒)。 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();
static int[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray();
static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray();
static string[] SList(long n) => Enumerable.Repeat(0, (int)n).Select(_ => ReadLine()).ToArray();
static long[] LList(long n) => Enumerable.Repeat(0, (int)n).Select(_ => long.Parse(ReadLine())).ToArray();
public static void Main()
{
Solve();
}
static void Solve()
{
var n = NN;
var s = NMi;
var t = NMi;
var u = NList;
var ts = new TwoSat(n * n);
for (var i = 0; i < n; ++i)
{
for (var j = 0; j < n; ++j)
{
// a_Si,j + 2 * a_j,Ti != Ui
ts.AddOrClause(s[i] * n + j, u[i] % 2 == 1, j * n + t[i], u[i] / 2 == 1);
}
}
var solve = ts.Solve();
if (solve.res)
{
var ans = new int[n][];
for (var i = 0; i < n; ++i)
{
ans[i] = new int[n];
for (var j = 0; j < n; ++j) ans[i][j] = solve.ans[i * n + j] ? 1 : 0;
}
WriteLine(string.Join("\n", ans.Select(ai => string.Join(" ", ai))));
}
else
{
WriteLine("-1");
}
}
/// <summary>
/// 有向グラフを作成し、強連結成分分解を行う
/// </summary>
/// <remarks>0 <= n <= 10^8
/// 0 <= from,to < n
/// SCCの計算量は O(n + m) m:辺の本数</remarks>
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;
}
}
}
/// <summary>SCCの応用：2-SAT</summary>
/// <remarks>
/// Xi == true, Xi == false に対応する頂点を用意し、
/// (Xi == true) or (Xj == false) を (Xi == false) -> (Xj == false), (Xj == true) -> (Xi == true) に変換して
/// グラフを作成し、SCCを求める
/// Xi == true と Xi == false が同じ連結成分にあったら実現不可
/// そうでないなら Xi == true と Xi == false のうちSCCIdの小さいほうを真とすればいい
/// </remarks>
class TwoSat
{
private int N;
private SCCGraph scc;
public TwoSat(int n)
{
N = n;
scc = new SCCGraph(n * 2);
}
public void AddOrClause(int xi, bool fi, int xj, bool fj)
{
scc.AddEdge(xi * 2 + (fi ? 1 : 0), xj * 2 + (fj ? 0 : 1));
scc.AddEdge(xj * 2 + (fj ? 1 : 0), xi * 2 + (fi ? 0 : 1));
}
public (bool res, bool[] ans) Solve()
{
var ans = new bool[N];
var (_, sccid) = scc.SCCIds();
for (var i = 0; i < N; ++i)
{
if (sccid[i * 2] == sccid[i * 2 + 1]) return (false, ans);
ans[i] = sccid[i * 2] < sccid[i * 2 + 1];
}
return (true, ans);
}
}
}