結果
問題 | 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_popcountusing 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;}