| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1295878 | AbdullahIshfaq | Connecting Supertrees (IOI20_supertrees) | C++20 | 0 ms | 0 KiB |
//by gpt :
// Compile: g++ -std=c++17 -O2 -pipe -o supertrees supertrees.cpp
#include <bits/stdc++.h>
using namespace std;
struct DSU {
int n;
vector<int> p;
DSU(int n=0): n(n), p(n) { for(int i=0;i<n;i++) p[i]=i; }
int find(int x){ return p[x]==x ? x : p[x]=find(p[x]); }
void unite(int a,int b){ a=find(a); b=find(b); if(a!=b) p[b]=a; }
bool same(int a,int b){ return find(a)==find(b); }
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if(!(cin>>n)) return 0;
vector<vector<int>> p(n, vector<int>(n));
for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>p[i][j];
// Basic checks: diagonal, symmetry, range
for(int i=0;i<n;i++){
if(p[i][i] != 1){
cout<<0<<"\n"; return 0;
}
for(int j=0;j<n;j++){
if(p[i][j] != p[j][i]){ cout<<0<<"\n"; return 0; }
if(p[i][j] < 0 || p[i][j] > 3){ cout<<0<<"\n"; return 0; }
if(i!=j && p[i][j] == 3){ // editorial: any '3' makes instance impossible
cout<<0<<"\n"; return 0;
}
}
}
// Build connectivity by p>0 (components)
DSU comp(n);
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++)
if(p[i][j] > 0) comp.unite(i,j);
// Consistency: within same DSU member p must be >0, otherwise p must be 0
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++){
bool sameComp = comp.same(i,j);
if(sameComp && p[i][j] == 0){ cout<<0<<"\n"; return 0; }
if(!sameComp && p[i][j] > 0){ cout<<0<<"\n"; return 0; }
}
// Output adjacency matrix to fill
vector<vector<int>> b(n, vector<int>(n, 0));
// For each component, process independently
vector<int> seenCompRep(n, 0);
for(int i=0;i<n;i++){
int r = comp.find(i);
if(seenCompRep[r]) continue;
seenCompRep[r] = 1;
// Collect nodes in this component
vector<int> nodes;
for(int v=0; v<n; ++v) if(comp.same(v, r)) nodes.push_back(v);
int m = (int)nodes.size();
if(m == 1) continue; // single node component, nothing to add
// Build DSU for "p==1" groups inside this component
unordered_map<int,int> idx; idx.reserve(m*2);
for(int t=0;t<m;t++) idx[nodes[t]] = t;
DSU eq(m);
for(int a=0;a<m;a++){
for(int b=a+1;b<m;b++){
int u = nodes[a], v = nodes[b];
if(p[u][v] == 1) eq.unite(a,b);
}
}
// Form groups
vector<int> repIndex(m, -1);
vector<vector<int>> groups;
for(int t=0;t<m;t++){
int root = eq.find(t);
if(repIndex[root] == -1){
repIndex[root] = (int)groups.size();
groups.push_back(vector<int>());
}
groups[ repIndex[root] ].push_back(nodes[t]);
}
// Validate: inside each group all pairs must have p==1
for(auto &g : groups){
for(size_t x=0; x<g.size(); ++x)
for(size_t y=x+1; y<g.size(); ++y)
if(p[g[x]][g[y]] != 1){ cout<<0<<"\n"; return 0; }
}
// Validate: pairs from distinct groups must have p==2
for(size_t gi=0; gi<groups.size(); ++gi){
for(size_t gj=gi+1; gj<groups.size(); ++gj){
for(int a : groups[gi]) for(int b : groups[gj]){
if(p[a][b] != 2){ cout<<0<<"\n"; return 0; }
}
}
}
// If there are exactly 2 groups, impossible (can't make 2-cycle)
if(groups.size() == 2){ cout<<0<<"\n"; return 0; }
// For each group, connect nodes in a chain (produces a tree for that group)
vector<int> reps; reps.reserve(groups.size());
for(auto &g : groups){
if(g.empty()) continue;
for(size_t t=1; t<g.size(); ++t){
int u = g[t-1], v = g[t];
b[u][v] = b[v][u] = 1;
}
reps.push_back(g[0]); // representative
}
// If >= 3 group-reps, connect them into a cycle
if(reps.size() >= 3){
int k = (int)reps.size();
for(int t=0; t<k; ++t){
int u = reps[t], v = reps[(t+1)%k];
b[u][v] = b[v][u] = 1;
}
}
// If reps.size()==1 => already done (a tree for the single group)
}
// Construction complete. Output result in required format.
cout<<1<<"\n";
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<b[i][j] << (j+1==n?'\n':' ');
}
}
return 0;
}