結果
問題 | No.1078 I love Matrix Construction |
ユーザー | kimiyuki |
提出日時 | 2020-06-12 22:00:58 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 331 ms / 2,000 ms |
コード長 | 5,533 bytes |
コンパイル時間 | 1,386 ms |
コンパイル使用メモリ | 110,860 KB |
実行使用メモリ | 51,692 KB |
最終ジャッジ日時 | 2023-09-06 10:27:49 |
合計ジャッジ時間 | 6,969 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 24 ms
10,324 KB |
testcase_03 | AC | 90 ms
21,496 KB |
testcase_04 | AC | 131 ms
28,456 KB |
testcase_05 | AC | 120 ms
24,212 KB |
testcase_06 | AC | 28 ms
9,828 KB |
testcase_07 | AC | 10 ms
5,804 KB |
testcase_08 | AC | 118 ms
24,368 KB |
testcase_09 | AC | 5 ms
4,380 KB |
testcase_10 | AC | 331 ms
51,692 KB |
testcase_11 | AC | 148 ms
30,056 KB |
testcase_12 | AC | 232 ms
43,148 KB |
testcase_13 | AC | 271 ms
48,092 KB |
testcase_14 | AC | 174 ms
34,204 KB |
testcase_15 | AC | 278 ms
45,748 KB |
testcase_16 | AC | 9 ms
5,148 KB |
testcase_17 | AC | 2 ms
4,380 KB |
testcase_18 | AC | 22 ms
8,300 KB |
testcase_19 | AC | 64 ms
14,844 KB |
testcase_20 | AC | 64 ms
14,512 KB |
testcase_21 | AC | 2 ms
4,376 KB |
ソースコード
#line 1 "main.cpp" #define PROBLEM "https://yukicoder.me/problems/no/1078" #include <cassert> #include <iostream> #line 2 "/home/user/Library/utils/macros.hpp" #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) #line 3 "/home/user/Library/utils/two_satisfiability.hpp" #include <utility> #include <vector> #line 2 "/home/user/Library/graph/strongly_connected_components.hpp" #include <functional> #line 4 "/home/user/Library/graph/transpose_graph.hpp" /** * @param g is an adjacent list of a digraph * @note $O(V + E)$ * @see https://en.wikipedia.org/wiki/Transpose_graph */ std::vector<std::vector<int> > make_transpose_graph(std::vector<std::vector<int> > const & g) { int n = g.size(); std::vector<std::vector<int> > h(n); REP (i, n) { for (int j : g[i]) { h[j].push_back(i); } } return h; } #line 7 "/home/user/Library/graph/strongly_connected_components.hpp" /** * @brief strongly connected components decomposition, Kosaraju's algorithm / 強連結成分分解 * @return the pair (the number k of components, the function from vertices of g to components) * @param g is an adjacent list of a digraph * @param g_rev is the transpose graph of g * @note $O(V + E)$ */ std::pair<int, std::vector<int> > decompose_to_strongly_connected_components(const std::vector<std::vector<int> > & g, const std::vector<std::vector<int> > & g_rev) { int n = g.size(); std::vector<int> acc(n); { std::vector<bool> used(n); std::function<void (int)> dfs = [&](int i) { used[i] = true; for (int j : g[i]) if (not used[j]) dfs(j); acc.push_back(i); }; REP (i,n) if (not used[i]) dfs(i); reverse(ALL(acc)); } int size = 0; std::vector<int> component_of(n); { std::vector<bool> used(n); std::function<void (int)> rdfs = [&](int i) { used[i] = true; component_of[i] = size; for (int j : g_rev[i]) if (not used[j]) rdfs(j); }; for (int i : acc) if (not used[i]) { rdfs(i); ++ size; } } return { size, move(component_of) }; } std::pair<int, std::vector<int> > decompose_to_strongly_connected_components(const std::vector<std::vector<int> > & g) { return decompose_to_strongly_connected_components(g, make_transpose_graph(g)); } #line 6 "/home/user/Library/utils/two_satisfiability.hpp" /** * @brief 2-SAT ($O(N)$) * @param n is the number of variables * @param cnf is a proposition in a conjunctive normal form. Each literal is expressed as number $x$ s.t. $1 \le \vert x \vert \le n$ * @return a vector with the length $n$ if SAT. It's empty if UNSAT. */ std::vector<bool> compute_two_satisfiability(int n, const std::vector<std::pair<int, int> > & cnf) { // make digraph std::vector<std::vector<int> > g(2 * n); auto index = [&](int x) { assert (x != 0 and abs(x) <= n); return x > 0 ? x - 1 : n - x - 1; }; for (auto it : cnf) { int x, y; std::tie(x, y) = it; // x or y g[index(- x)].push_back(index(y)); // not x implies y g[index(- y)].push_back(index(x)); // not y implies x } // do SCC std::vector<int> component = decompose_to_strongly_connected_components(g).second; std::vector<bool> valuation(n); REP3 (x, 1, n + 1) { if (component[index(x)] == component[index(- x)]) { // x iff not x return std::vector<bool>(); // unsat } valuation[x - 1] = component[index(x)] > component[index(- x)]; // use components which indices are large } return valuation; } #line 6 "main.cpp" using namespace std; vector<vector<bool> > solve(int n, vector<int> & s, vector<int> & t, vector<int> & u) { auto var = [&](int y, int x) { return y * n + x; }; vector<pair<int, int> > cnf; REP (y, n) { REP (x, n) { int a = var(s[y], x) + 1; int b = var(x, t[y]) + 1; if (u[y] == 0) { cnf.emplace_back(a, b); } else if (u[y] == 1) { cnf.emplace_back(- a, b); } else if (u[y] == 2) { cnf.emplace_back(a, - b); } else if (u[y] == 3) { cnf.emplace_back(- a, - b); } else { assert (false); } } } auto ev = compute_two_satisfiability(n * n, cnf); if (ev.empty()) { return vector<vector<bool> >(); } else { vector<vector<bool> > a(n, vector<bool>(n)); REP (y, n) { REP (x, n) { a[y][x] = ev[var(y, x)]; } } return a; } } int main() { // input int n; scanf("%d", &n); vector<int> s(n); REP (i, n) { scanf("%d", &s[i]); -- s[i]; } vector<int> t(n); REP (i, n) { scanf("%d", &t[i]); -- t[i]; } vector<int> u(n); REP (i, n) { scanf("%d", &u[i]); } // solve auto a = solve(n, s, t, u); // output if (a.empty()) { printf("%d\n", -1); } else { REP (y, n) { REP (x, n) { printf("%d%c", (int)a[y][x], x + 1 < n ? ' ' : '\n'); } } } return 0; }