# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1073407 | 2024-08-24T14:11:16 Z | blushingecchigirl | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define pb push_back struct dsu { vector<int> parent, rank; int size; dsu(int sz) { size = sz; rank.assign(size, 1); parent.resize(size); for(int i = 0; i<size; i++) parent[i] = i; } int search(int v) { if(v == parent[v]) return v; return parent[v] = search(parent[v]); } void connect(int v, int u) { v = search(v); u = search(u); if(v == u) return; if(rank[v]>=rank[u]) parent[u] = v; else parent[v] = u; if(rank[v] == rank[u]) rank[v]++; return; } }; void solve() { int n; cin>>n; int p[n][n]{}; bool construct = 1, b[n][n]{}; vector<int> a[n]; dsu d = dsu(n); for(int i = 0; i<n; i++) { for(int j = 0; j<n; j++) { cin>>p[i][j]; if(p[i][j]) d.connect(i, j); } } for(int i = 0; i<n; i++) { a[d.search(i)].pb(i); } for(int i = 0; i<n; i++) { if(a[i].size()<=1) continue; int pth = p[a[i][0]][a[i][1]]; for(int ii:a[i]) { for(int j:a[i]) { if(ii == j) continue; if(p[ii][j] != pth) construct = false; } } for(size_t ii = 1; ii<a[i].size(); ii++) { b[ii][ii-1] = b[ii-1][ii] = 1; } if(pth == 2) b[a[i][0]][a[i].back()] = b[a[i].back()][a[i][0]] = 1; } cout << construct << '\n'; if(construct) { for(int i = 0; i<n; i++) { for(int j = 0; j<n; j++) cout << b[i][j] << ' '; cout << '\n'; } } } int main() { ios::sync_with_stdio(0); cin.tie(0); int t = 1; // cin>>t; while(t--) solve(); return 0; }