結果
問題 | No.1078 I love Matrix Construction |
ユーザー | risujiroh |
提出日時 | 2020-06-12 23:16:08 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 300 ms / 2,000 ms |
コード長 | 4,135 bytes |
コンパイル時間 | 2,500 ms |
コンパイル使用メモリ | 216,260 KB |
実行使用メモリ | 59,444 KB |
最終ジャッジ日時 | 2023-09-06 11:19:55 |
合計ジャッジ時間 | 7,832 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 31 ms
11,612 KB |
testcase_03 | AC | 91 ms
24,928 KB |
testcase_04 | AC | 138 ms
32,424 KB |
testcase_05 | AC | 117 ms
28,520 KB |
testcase_06 | AC | 27 ms
11,532 KB |
testcase_07 | AC | 10 ms
6,180 KB |
testcase_08 | AC | 114 ms
29,368 KB |
testcase_09 | AC | 5 ms
4,384 KB |
testcase_10 | AC | 300 ms
59,444 KB |
testcase_11 | AC | 145 ms
34,252 KB |
testcase_12 | AC | 233 ms
53,444 KB |
testcase_13 | AC | 273 ms
57,144 KB |
testcase_14 | AC | 176 ms
42,144 KB |
testcase_15 | AC | 264 ms
55,580 KB |
testcase_16 | AC | 8 ms
5,556 KB |
testcase_17 | AC | 1 ms
4,376 KB |
testcase_18 | AC | 19 ms
9,112 KB |
testcase_19 | AC | 52 ms
16,780 KB |
testcase_20 | AC | 50 ms
16,492 KB |
testcase_21 | AC | 3 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define DEBUG(...) #endif template <typename T> class graph { public: struct edge { int from; int to; T cost; }; vector<edge> edges; vector< vector<int> > g; int n; function<bool(int)> ignore; graph(int _n) : n(_n) { g.resize(n); ignore = nullptr; } virtual int add(int from, int to, T cost) = 0; virtual void set_ignore_edge_rule(const function<bool(int)> &f) { ignore = f; } virtual void reset_ignore_edge_rule() { ignore = nullptr; } }; template <typename T> class digraph : public graph<T> { public: using graph<T>::edges; using graph<T>::g; using graph<T>::n; using graph<T>::ignore; digraph(int _n) : graph<T>(_n) { } int add(int from, int to, T cost = 1) { assert(0 <= from && from < n && 0 <= to && to < n); int id = (int) edges.size(); g[from].push_back(id); edges.push_back({from, to, cost}); return id; } digraph<T> reverse() const { digraph<T> rev(n); for (auto &e : edges) { rev.add(e.to, e.from, e.cost); } if (ignore != nullptr) { rev.set_ignore_edge_rule([&](int id) { return ignore(id); }); } return rev; } }; template <typename T> vector<int> find_scc(const digraph<T> &g, int &cnt) { digraph<T> g_rev = g.reverse(); vector<int> order; vector<bool> was(g.n, false); function<void(int)> dfs1 = [&](int v) { was[v] = true; for (int id : g.g[v]) { if (g.ignore != nullptr && g.ignore(id)) { continue; } auto &e = g.edges[id]; int to = e.to; if (!was[to]) { dfs1(to); } } order.push_back(v); }; for (int i = 0; i < g.n; i++) { if (!was[i]) { dfs1(i); } } vector<int> c(g.n, -1); function<void(int)> dfs2 = [&](int v) { for (int id : g_rev.g[v]) { if (g_rev.ignore != nullptr && g_rev.ignore(id)) { continue; } auto &e = g_rev.edges[id]; int to = e.to; if (c[to] == -1) { c[to] = c[v]; dfs2(to); } } }; cnt = 0; for (int id = g.n - 1; id >= 0; id--) { int i = order[id]; if (c[i] != -1) { continue; } c[i] = cnt++; dfs2(i); } return c; // c[i] <= c[j] for every edge i -> j } class twosat { public: digraph<int> g; int n; twosat(int _n) : g(digraph<int>(2 * _n)), n(_n) { } inline void add(int x, int value_x) { // (v[x] == value_x) assert(0 <= x && x < n); assert(0 <= value_x && value_x <= 1); g.add(2 * x + (value_x ^ 1), 2 * x + value_x); } inline void add(int x, int value_x, int y, int value_y) { // (v[x] == value_x || v[y] == value_y) assert(0 <= x && x < n && 0 <= y && y < n); assert(0 <= value_x && value_x <= 1 && 0 <= value_y && value_y <= 1); g.add(2 * x + (value_x ^ 1), 2 * y + value_y); g.add(2 * y + (value_y ^ 1), 2 * x + value_x); } inline vector<int> solve() { int cnt; vector<int> c = find_scc(g, cnt); vector<int> res(n); for (int i = 0; i < n; i++) { if (c[2 * i] == c[2 * i + 1]) { return vector<int>(); } res[i] = (c[2 * i] < c[2 * i + 1]); } return res; } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; vector<int> s(n), t(n), u(n); for (auto&& e : s) cin >> e, --e; for (auto&& e : t) cin >> e, --e; for (auto&& e : u) cin >> e; auto _ = [&](int i, int j) { return i * n + j; }; twosat ts(n * n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (u[i] == 0) { ts.add(_(s[i], j), 1, _(j, t[i]), 1); } else if (u[i] == 1) { ts.add(_(s[i], j), 0, _(j, t[i]), 1); } else if (u[i] == 2) { ts.add(_(s[i], j), 1, _(j, t[i]), 0); } else { ts.add(_(s[i], j), 0, _(j, t[i]), 0); } } } auto res = ts.solve(); if (empty(res)) { cout << "-1\n"; } else { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cout << res[_(i, j)] << " \n"[j == n - 1]; } } } }