結果

問題 No.1078 I love Matrix Construction
ユーザー 夜夜
提出日時 2021-03-19 20:04:27
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 4,094 bytes
コンパイル時間 1,462 ms
コンパイル使用メモリ 113,880 KB
実行使用メモリ 40,396 KB
最終ジャッジ日時 2024-04-29 14:13:44
合計ジャッジ時間 5,595 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
21,888 KB
testcase_01 AC 11 ms
21,888 KB
testcase_02 AC 39 ms
29,108 KB
testcase_03 AC 108 ms
40,396 KB
testcase_04 RE -
testcase_05 RE -
testcase_06 AC 44 ms
28,588 KB
testcase_07 AC 20 ms
24,576 KB
testcase_08 RE -
testcase_09 AC 15 ms
23,040 KB
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 AC 20 ms
24,192 KB
testcase_17 AC 10 ms
22,016 KB
testcase_18 AC 29 ms
27,108 KB
testcase_19 AC 83 ms
33,912 KB
testcase_20 AC 70 ms
33,496 KB
testcase_21 AC 13 ms
22,400 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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[200020] = { false }, bo1[200020] = { false };
vector<vector<int>> vec(200020), vec1(200020);
vector<vector<int>> ans(200020), ans_vec(200020);
int ans1[200020];
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;
	}
}
0