結果

問題 No.1078 I love Matrix Construction
ユーザー masutech16
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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_COMPONENTS
class 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0