結果
| 問題 | No.1078 I love Matrix Construction |
| ユーザー |
 夜
|
| 提出日時 | 2021-03-19 20:11:35 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 463 ms / 2,000 ms |
| コード長 | 4,094 bytes |
| コンパイル時間 | 1,305 ms |
| コンパイル使用メモリ | 113,772 KB |
| 実行使用メモリ | 97,124 KB |
| 最終ジャッジ日時 | 2024-11-18 18:59:22 |
| 合計ジャッジ時間 | 7,696 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 22 |
ソースコード
#include <iostream>#include <string>#include <algorithm>#include <vector>#include <iomanip>#include <cmath>#include <stdio.h>#include <queue>#include <deque>#include <cstdio>#include <set>#include <map>#include <bitset>#include <stack>#include <cctype>using namespace std;int n, m;bool bo[500020] = { false }, bo1[500020] = { false };vector<vector<int>> vec(500020), vec1(500020);vector<vector<int>> ans(500020), ans_vec(500020);int ans1[500020];int ans_g[200020] = {};void scc() {vector<pair<int, int>> mem_co;stack<int> st;int co = 1;for (int i = 0; i < n; i++) {if (!bo[i]) {st.push(i);bo[i] = true;while (!st.empty()) {int now = st.top();bool stb = false;for (int j = 0; j < vec[now].size(); j++) {if (!bo[vec[now][j]]) {bo[vec[now][j]] = true;stb = true;st.push(vec[now][j]);break;}}if (!stb) {mem_co.emplace_back(make_pair(co, now));co++;st.pop();}}}}for (int i = 0; i < n; i++) {bo[i] = false;}sort(mem_co.rbegin(), mem_co.rend());co = 0;for (int i = 0; i < n; i++) {if (!bo[mem_co[i].second]) {st.push(mem_co[i].second);bo[mem_co[i].second] = true;while (!st.empty()) {int now = st.top();st.pop();ans[co].emplace_back(now);ans1[now] = co;for (int j = 0; j < vec1[now].size(); j++) {if (!bo[vec1[now][j]]) {bo[vec1[now][j]] = true;st.push(vec1[now][j]);}else if (ans1[vec1[now][j]] != ans1[now]) {ans_vec[ans1[vec1[now][j]]].emplace_back(ans1[now]);}}}sort(ans[co].begin(), ans[co].end());co++;}}}int co[200020] = {};int ans_tp[200020];void tp_sort() {queue<int>que;for (int i = 0; i < n; i++) {if (co[i] == 0) {que.push(i);}}int now = 0;while (!que.empty()) {int k = que.front();ans_tp[now] = k;now++;for (int l = 0; l < ans_vec[k].size(); l++) {co[ans_vec[k][l]]--;if (co[ans_vec[k][l]] == 0) {que.push(ans_vec[k][l]);}}que.pop();}}int s1[550], t1[550], u1[550];int main() {int n1;cin >> n1;n = n1 * n1 * 2;for (int i = 0; i < n1; i++) {cin >> s1[i];}for (int i = 0; i < n1; i++) {cin >> t1[i];}for (int i = 0; i < n1; i++) {cin >> u1[i];}for (int i = 0; i < n1; i++) {int s = s1[i], t = t1[i], u = u1[i];s--, t--;for (int j = 0; j < n1; j++) {if (u == 0) {vec[s + j * n1].emplace_back(j + t * n1 + n1 * n1);vec1[j + t * n1 + n1 * n1].emplace_back(s + j * n1);vec[j + t * n1].emplace_back(s + j * n1 + n1 * n1);vec1[s + j * n1 + n1 * n1].emplace_back(j + t * n1);}if (u == 1) {vec[s + j * n1 + n1 * n1].emplace_back(j + t * n1 + n1 * n1);vec1[j + t * n1 + n1 * n1].emplace_back(s + j * n1 + n1 * n1);vec[j + t * n1].emplace_back(s + j * n1);vec1[s + j * n1].emplace_back(j + t * n1);}if (u == 2) {vec[s + j * n1].emplace_back(j + t * n1);vec1[j + t * n1].emplace_back(s + j * n1);vec[j + t * n1 + n1 * n1].emplace_back(s + j * n1 + n1 * n1);vec1[s + j * n1 + n1 * n1].emplace_back(j + t * n1 + n1 * n1);}if (u == 3) {vec[s + j * n1 + n1 * n1].emplace_back(j + t * n1);vec1[j + t * n1].emplace_back(s + j * n1 + n1 * n1);vec[j + t * n1 + n1 * n1].emplace_back(s + j * n1);vec1[s + j * n1].emplace_back(j + t * n1 + n1 * n1);}}}scc();for (int i = 0; i < n; i++) {for (int j = 0; j < ans_vec[i].size(); j++) {co[ans_vec[i][j]]++;}}tp_sort();for (int i = 0; i < n; i++) {if (i < n1 * n1 && ans1[i] == ans1[i + n1 * n1]) {cout << "-1" << endl;return 0;}for (int j = 0; j < ans[ans_tp[i]].size(); j++) {bo1[ans[ans_tp[i]][j]] = true;if (ans[ans_tp[i]][j] >= n1 * n1) {if (!bo1[ans[ans_tp[i]][j] - n1 * n1]) {ans_g[ans[ans_tp[i]][j] - n1 * n1] = 0;}else {ans_g[ans[ans_tp[i]][j] - n1 * n1] = 1;}}}}for (int i = 0; i < n1; i++) {for (int j = 0; j < n1; j++) {cout << ans_g[i + j * n1] << " ";}cout << endl;}}