結果
問題 | No.1078 I love Matrix Construction |
ユーザー |
![]() |
提出日時 | 2020-06-12 22:53:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 410 ms / 2,000 ms |
コード長 | 2,210 bytes |
コンパイル時間 | 2,067 ms |
コンパイル使用メモリ | 134,372 KB |
最終ジャッジ日時 | 2025-01-11 02:51:34 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; struct SCC{ vector<vector<int>> g, gr; int n, k; vector<int> cmp, vs; vector<bool> used; void dfs(int x){ used[x]=1; for(auto y:g[x]){ if(!used[y]) dfs(y); } vs.push_back(x); } void rdfs(int v, int k){ used[v]=1; cmp[v]=k; for(auto y:gr[v]){ if(!used[y]) rdfs(y, k); } } SCC(const vector<vector<int>> &g):g(g), n(g.size()), cmp(n), used(n){ gr.resize(n); for(int x=0; x<n; x++) for(auto y:g[x]) gr[y].push_back(x); for(int i=0; i<n; i++){ if(!used[i]) dfs(i); } fill(used.begin(), used.end(), 0); k=0; for(int i=vs.size()-1; i>=0; i--){ if(!used[vs[i]]) rdfs(vs[i], k++); } } }; int main() { int n; cin>>n; int s[505], t[505], u[505]; for(int i=0; i<n; i++) cin>>s[i], s[i]--; for(int i=0; i<n; i++) cin>>t[i], t[i]--; for(int i=0; i<n; i++) cin>>u[i]; vector<vector<int>> g(2*n*n); for(int i=0; i<n; i++){ int p=(u[i]&1), q=(u[i]>>1); for(int j=0; j<n; j++){ int x=s[i]*n+j, y=j*n+t[i]; g[x+p*n*n].push_back(y+(q^1)*n*n); g[y+q*n*n].push_back(x+(p^1)*n*n); } } SCC scc(g); int a[505][505]; for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ if(scc.cmp[i*n+j]==scc.cmp[i*n+j+n*n]){ cout<<-1<<endl; return 0; }else if(scc.cmp[i*n+j]<scc.cmp[i*n+j+n*n]){ a[i][j]=1; }else{ a[i][j]=0; } } } for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ assert(a[s[i]][j]+a[j][t[i]]*2!=u[i]); } } for(int i=0; i<n; i++){ for(int j=0; j<n; j++) cout<<a[i][j]<<" "; cout<<endl; } return 0; }