結果
問題 | No.1078 I love Matrix Construction |
ユーザー | Haar |
提出日時 | 2020-06-17 14:10:31 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,876 bytes |
コンパイル時間 | 2,567 ms |
コンパイル使用メモリ | 225,412 KB |
実行使用メモリ | 54,772 KB |
最終ジャッジ日時 | 2023-09-16 11:25:58 |
合計ジャッジ時間 | 7,836 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 22 ms
10,728 KB |
testcase_03 | AC | 60 ms
22,568 KB |
testcase_04 | AC | 88 ms
30,004 KB |
testcase_05 | WA | - |
testcase_06 | AC | 20 ms
10,212 KB |
testcase_07 | AC | 8 ms
5,908 KB |
testcase_08 | AC | 71 ms
25,868 KB |
testcase_09 | WA | - |
testcase_10 | AC | 223 ms
54,772 KB |
testcase_11 | AC | 93 ms
31,636 KB |
testcase_12 | AC | 162 ms
45,388 KB |
testcase_13 | AC | 182 ms
51,280 KB |
testcase_14 | AC | 117 ms
36,136 KB |
testcase_15 | AC | 169 ms
48,884 KB |
testcase_16 | WA | - |
testcase_17 | AC | 2 ms
4,376 KB |
testcase_18 | AC | 16 ms
8,708 KB |
testcase_19 | AC | 36 ms
15,704 KB |
testcase_20 | AC | 37 ms
15,508 KB |
testcase_21 | WA | - |
ソースコード
#include <bits/stdc++.h> /** * @title Graph template * @docs graph_template.md */ template <typename Cost = int> class Edge{ public: int from,to; Cost cost; Edge() {} Edge(int to, Cost cost): to(to), cost(cost){} Edge(int from, int to, Cost cost): from(from), to(to), cost(cost){} }; template <typename T> using Graph = std::vector<std::vector<Edge<T>>>; template <typename T> using Tree = std::vector<std::vector<Edge<T>>>; template <typename T, typename C> void add_edge(C &g, int from, int to, T w = 1){ g[from].emplace_back(from, to, w); } template <typename T, typename C> void add_undirected(C &g, int a, int b, T w = 1){ add_edge<T, C>(g, a, b, w); add_edge<T, C>(g, b, a, w); } /** * @title Topological sort * @docs topological_sort.md */ template <typename T> std::optional<std::vector<int>> topological_sort(const Graph<T> &g){ const int n = g.size(); std::vector<int> indeg(n); for(int i = 0; i < n; ++i){ for(auto &e : g[i]){ ++indeg[e.to]; } } std::queue<int> q; for(int i = n-1; i >= 0; --i){ if(indeg[i] == 0) q.push(i); } std::vector<int> ret; while(!q.empty()){ int cur = q.front(); q.pop(); ret.push_back(cur); for(auto &e : g[cur]){ --indeg[e.to]; if(indeg[e.to] == 0){ q.push(e.to); } } } if((int)ret.size() == n){ return {ret}; }else{ return std::nullopt; } } /** * @title Strongly connected components * @docs strongly_connected_components.md */ template <typename T> auto strongly_connected_components(const Graph<T> &g){ const int n = g.size(); std::vector<bool> visit(n); std::vector<int> check(n); std::vector<int> result(n, -1); auto dfs = [&](auto &f, int cur) -> void { visit[cur] = true; for(const auto &e : g[cur]){ if(not visit[e.to]) f(f, e.to); } check.push_back(cur); }; for(int i = 0; i < n; ++i) if(not visit[i]) dfs(dfs, i); std::reverse(check.begin(), check.end()); Graph<T> rg(n); auto rdfs = [&](auto &f, int cur, int i) -> void { result[cur] = i; for(const auto &e : rg[cur]){ if(result[e.to] == -1) f(f, e.to, i); } }; for(int i = 0; i < n; ++i) for(const auto &e : g[i]) rg[e.to].emplace_back(e.to, e.from, e.cost); int i = 0; for(auto c : check) if(result[c] == -1) rdfs(rdfs, c, i), ++i; return std::make_pair(result, i); } /** * @title 2-SAT * @docs two_sat.md */ class TwoSat{ const int n; Graph<int> g; int f(int i){ assert(i != 0); assert(abs(i) <= n); if(i > 0) return i-1; else return abs(i)-1 + n; } public: TwoSat(int n): n(n), g(2*n){} /** * @note a→bを導入する */ void add_if(int a, int b){ add_edge(g, f(a), f(b), 1); } /** * @note a∨bを導入する * @note a ∨ b <=> (!a => b) ∧ (!b => a) */ void add_or(int a, int b){ add_if(-a, b); add_if(-b, a); } /** * @note ¬(a∧b)を導入する * @note !(A ∧ B) <=> (!A ∨ !B) */ void not_coexist(int a, int b){ add_or(-a, -b); } public: std::optional<std::vector<bool>> solve() const { auto [scc, m] = strongly_connected_components<int>(g); for(int i = 0; i < n; ++i){ if(scc[i] == scc[i+n]) return {}; } Graph<int> g2(m); for(int i = 0; i < 2*n; ++i){ for(auto &e : g[i]){ if(scc[e.from] != scc[e.to]){ add_edge(g2, scc[e.from], scc[e.to], 1); } } } auto ts = *topological_sort(g2); std::vector<int> r(m); for(int i = 0; i < m; ++i) r[ts[i]] = i; std::vector<bool> ret(n); for(int i = 0; i < n; ++i) ret[i] = r[scc[i]] > r[scc[i+n]]; return {ret}; } }; int main(){ int N; std::cin >> N; std::vector<int> S(N), T(N), U(N); for(int i = 0; i < N; ++i) std::cin >> S[i], --S[i]; for(int i = 0; i < N; ++i) std::cin >> T[i], --T[i]; for(int i = 0; i < N; ++i) std::cin >> U[i]; TwoSat sat(N*N); auto index = std::vector(N, std::vector<int>(N)); { int k = 1; for(int i = 0; i < N; ++i){ for(int j = 0; j < N; ++j){ index[i][j] = k; ++k; } } } for(int i = 0; i < N; ++i){ for(int j = 0; j < N; ++j){ switch(U[i]){ case 0: sat.not_coexist(-index[S[i]][j], -index[j][T[i]]); break; case 1: sat.not_coexist(index[S[i]][j], -index[j][T[i]]); break; case 2: sat.not_coexist(-index[S[i]][j], -index[j][T[i]]); break; case 3: sat.not_coexist(index[S[i]][j], index[j][T[i]]); break; } } } auto res = sat.solve(); if(res){ for(int i = 0; i < N; ++i){ for(int j = 0; j < N; ++j){ std::cout << (*res)[index[i][j]-1] << " "; } std::cout << "\n"; } }else{ std::cout << -1 << "\n"; } return 0; }