結果

問題 No.1078 I love Matrix Construction
ユーザー 夜夜
提出日時 2021-03-19 20:11:35
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 480 ms / 2,000 ms
コード長 4,094 bytes
コンパイル時間 1,453 ms
コンパイル使用メモリ 115,532 KB
実行使用メモリ 97,128 KB
最終ジャッジ日時 2024-04-29 14:41:17
合計ジャッジ時間 8,078 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 27 ms
50,176 KB
testcase_01 AC 27 ms
50,176 KB
testcase_02 AC 62 ms
57,236 KB
testcase_03 AC 160 ms
68,404 KB
testcase_04 AC 249 ms
75,236 KB
testcase_05 AC 223 ms
71,964 KB
testcase_06 AC 73 ms
56,716 KB
testcase_07 AC 50 ms
52,736 KB
testcase_08 AC 205 ms
70,896 KB
testcase_09 AC 43 ms
51,328 KB
testcase_10 AC 480 ms
97,128 KB
testcase_11 AC 228 ms
76,712 KB
testcase_12 AC 414 ms
89,148 KB
testcase_13 AC 450 ms
93,596 KB
testcase_14 AC 268 ms
80,568 KB
testcase_15 AC 427 ms
91,824 KB
testcase_16 AC 33 ms
52,232 KB
testcase_17 AC 22 ms
50,048 KB
testcase_18 AC 50 ms
55,368 KB
testcase_19 AC 90 ms
61,916 KB
testcase_20 AC 84 ms
61,500 KB
testcase_21 AC 23 ms
50,508 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[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;
	}
}
0