結果
問題 | No.1078 I love Matrix Construction |
ユーザー |
|
提出日時 | 2020-06-17 14:10:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,876 bytes |
コンパイル時間 | 3,004 ms |
コンパイル使用メモリ | 218,372 KB |
最終ジャッジ日時 | 2025-01-11 04:58:14 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 WA * 4 |
ソースコード
#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; }