結果
問題 | No.1078 I love Matrix Construction |
ユーザー |
|
提出日時 | 2020-06-22 22:14:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,239 bytes |
コンパイル時間 | 2,103 ms |
コンパイル使用メモリ | 182,436 KB |
実行使用メモリ | 47,852 KB |
最終ジャッジ日時 | 2024-07-03 18:56:23 |
合計ジャッジ時間 | 6,832 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 WA * 4 |
ソースコード
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/graph/SCC.hpp"#include <cassert>#include <iostream>#include <vector>#ifndef STRONGLY_CONNECTED_COMPONENTS#define STRONGLY_CONNECTED_COMPONENTSclass StronglyConnectedComponents {public:StronglyConnectedComponents(const std::vector<std::vector<int>> &g) {int n = g.size();std::vector<std::vector<int>> rg(n);for (int i = 0; i < n; i++) {for (const auto &v : g[i]) {rg[v].push_back(i);}}int now_id = 0;std::vector<int> id(n);std::vector<bool> visited(n, false);for (int i = 0; i < n; i++) {now_id = dfs(i, now_id, id, visited, g);}int comp_id = 0;visited.assign(n, false);components_id.resize(n);for (int i = n - 1; i >= 0; i--) {rdfs(id[i], comp_id, visited, rg);comp_id++;}}int get(int i) const {assert(0 <= i && i < static_cast<int>(components_id.size()));return components_id[i];}private:int dfs(int cur, int now_id, std::vector<int> &id, std::vector<bool> &visited,const std::vector<std::vector<int>> &g) {if (visited[cur])return now_id;visited[cur] = true;for (const auto &v : g[cur]) {now_id = dfs(v, now_id, id, visited, g);}id[now_id] = cur;now_id++;return now_id;}void rdfs(int cur, int comp_id, std::vector<bool> &visited, const std::vector<std::vector<int>> &g) {if (visited[cur])return;visited[cur] = true;components_id[cur] = comp_id;for (const auto v : g[cur]) {rdfs(v, comp_id, visited, g);}}std::vector<int> components_id;};using SCC = StronglyConnectedComponents;#endif#line 1 "/mnt/c/Users/leafc/dev/compro/lib/template.hpp"#include <bits/stdc++.h>#define REP(i, n) for (int i = 0; i < n; i++)#define FOR(i, m, n) for (int i = m; i < n; i++)#define ALL(v) (v).begin(), (v).end()#define coutd(n) cout << fixed << setprecision(n)#define ll long long int#define vl vector<ll>#define vi vector<int>#define MM << " " <<using namespace std;template <class T> void say(bool val, T yes, T no) { cout << (val ? yes : no) << "\n"; }void say(bool val, string yes = "Yes", string no = "No") { say<string>(val, yes, no); }template <class T> void chmin(T &a, T b) {if (a > b)a = b;}template <class T> void chmax(T &a, T b) {if (a < b)a = b;}// C++ 17に完全移行したら消す// 最大公約数を求めるtemplate <class T> T gcd(T n, T m) { return n ? gcd(m % n, n) : m; }// 最小公倍数を求めるtemplate <class T> T lcm(T n, T m) {int g = gcd(n, m);return n * m / g;}// 重複を消す。計算量はO(NlogN)template <class T> void unique(std::vector<T> &v) {std::sort(v.begin(), v.end());v.erase(std::unique(v.begin(), v.end()), v.end());}#line 3 "tmp.cpp"int n;int calc(int i, int j, bool b) { return i * n + j + (b ? 0 : n * n); }int main() {cin.tie(0);ios::sync_with_stdio(false);cin >> n;vi s(n), t(n), u(n);REP(i, n) {cin >> s[i];s[i]--;}REP(i, n) {cin >> t[i];t[i]--;}REP(i, n) { cin >> u[i]; }vector<vector<int>> g(2 * n * n);REP(i, n) {REP(j, n) {if (u[i] == 0) {g[calc(s[i], j, false)].push_back(calc(j, t[i], true));g[calc(j, t[i], false)].push_back(calc(s[i], j, true));} else if (u[i] == 1) {g[calc(s[i], j, true)].push_back(calc(j, t[i], true));g[calc(j, t[i], false)].push_back(calc(s[i], j, false));} else if (u[i] == 2) {g[calc(s[i], j, false)].push_back(calc(j, t[i], true));g[calc(j, t[i], true)].push_back(calc(s[i], j, true));} else if (u[i] == 3) {g[calc(s[i], j, true)].push_back(calc(j, t[i], false));g[calc(j, t[i], true)].push_back(calc(s[i], j, false));}}}SCC scc(g);REP(i, n * n) {if (scc.get(i) == scc.get(n * n + i)) {cout << -1 << endl;return 0;}}vi ans(n * n, -1);REP(i, n * n) {if (scc.get(i) < scc.get(n * n + i)) {ans[i] = 1;} else {ans[i] = 0;}}REP(i, n) {REP(j, n) { cout << ans[i * n + j] << (j == n - 1 ? "\n" : " "); }}return 0;}