結果
問題 | No.1078 I love Matrix Construction |
ユーザー | yukudo |
提出日時 | 2020-06-13 01:39:09 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 201 ms / 2,000 ms |
コード長 | 2,868 bytes |
コンパイル時間 | 1,931 ms |
コンパイル使用メモリ | 177,356 KB |
実行使用メモリ | 48,100 KB |
最終ジャッジ日時 | 2023-09-06 11:39:12 |
合計ジャッジ時間 | 5,966 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 18 ms
9,824 KB |
testcase_03 | AC | 56 ms
20,392 KB |
testcase_04 | AC | 118 ms
26,520 KB |
testcase_05 | AC | 68 ms
22,724 KB |
testcase_06 | AC | 18 ms
9,788 KB |
testcase_07 | AC | 7 ms
5,700 KB |
testcase_08 | AC | 66 ms
22,944 KB |
testcase_09 | AC | 4 ms
4,380 KB |
testcase_10 | AC | 201 ms
48,100 KB |
testcase_11 | AC | 98 ms
28,072 KB |
testcase_12 | AC | 160 ms
40,276 KB |
testcase_13 | AC | 164 ms
44,780 KB |
testcase_14 | AC | 95 ms
32,572 KB |
testcase_15 | AC | 160 ms
42,872 KB |
testcase_16 | AC | 6 ms
5,180 KB |
testcase_17 | AC | 1 ms
4,376 KB |
testcase_18 | AC | 13 ms
8,224 KB |
testcase_19 | AC | 32 ms
14,244 KB |
testcase_20 | AC | 27 ms
13,876 KB |
testcase_21 | AC | 3 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i) #define ALL(v) (v).begin(),(v).end() #define CLR(t,v) memset(t,(v),sizeof(t)) template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";} template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;} template<class T>void chmin(T&a,const T&b){if(a>b)a=b;} template<class T>void chmax(T&a,const T&b){if(a<b)a=b;} ll nextLong() { ll x; scanf("%lld", &x); return x;} struct TwoSAT { const int N; vector<vector<int>> g, r; TwoSAT(int N): N(N) { g = vector<vector<int>>(2*N); r = vector<vector<int>>(2*N); } // (a == a_val || b == b_val) void add_cond(int a, bool a_val, int b, bool b_val) { int x = 2 * a + (a_val ? 1 : 0); int y = 2 * b + (b_val ? 1 : 0); g[x^1].push_back(y); g[y^1].push_back(x); r[y].push_back(x^1); r[x].push_back(y^1); } // !(a == a_val && b == b_val) void add_forbid(int a, bool a_val, int b, bool b_val) { add_cond(a, !a_val, b, !b_val); } vector<int> sccid; int sccnum; void dfs(int p, vector<int>& order) { if (sccid[p] != 0) return; sccid[p] = 1; for (int i : g[p]) dfs(i, order); order.push_back(p); } void rdfs(int p, int id) { if (sccid[p] != -1) return; sccid[p] = id; for (int i : r[p]) rdfs(i, id); } void scc() { sccnum = 0; sccid = vector<int>(2 * N); vector<int> order; REP(i, 2*N) dfs(i, order); fill(ALL(sccid), -1); sccnum = 0; for (int i = (int)order.size() - 1; i >= 0; i--) if (sccid[order[i]] == -1) { rdfs(order[i], sccnum); sccnum++; } } // 割り当てを一つ返す。存在しない場合は長さ0を返す。 vector<int> solve() { vector<int> res(N); REP(i, N) { if (sccid[2*i] != -1 && sccid[2*i] == sccid[2*i+1]) return {}; res[i] = sccid[2*i+1] > sccid[2*i] ? 1 : 0; } return res; } }; const int MAX_N = 505; int A[MAX_N][MAX_N]; int N; int nodeId(int r, int c) { return (r * N + c); } int main2() { N = nextLong(); vector<int> S(N), T(N), U(N); REP(i, N) S[i] = nextLong()-1; REP(i, N) T[i] = nextLong()-1; REP(i, N) U[i] = nextLong(); TwoSAT twoSAT(N*N); REP(i, N) REP(j, N) { twoSAT.add_forbid(nodeId(S[i], j), U[i] & 1, nodeId(j, T[i]), U[i] >> 1); } twoSAT.scc(); auto res = twoSAT.solve(); if (res.size() == 0) { cout << -1 << endl; } else { REP(i, N*N) { int r = i / N; int c = i % N; A[r][c] = res[i]; } REP(r, N) { REP(c, N) { if (c) cout << ' '; cout << A[r][c]; } cout << '\n'; } } return 0; } int main() { #ifdef LOCAL for (;!cin.eof();cin>>ws) #endif main2(); return 0; }