| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1295882 | AbdullahIshfaq | Connecting Supertrees (IOI20_supertrees) | C++20 | 0 ms | 0 KiB |
// GPT code
// Supertrees - constructive solution for the sample grader format
// Reads n and matrix p, prints 0 if impossible.
// Otherwise prints 1 and an adjacency matrix b (0/1) for a valid simple undirected graph.
//
// Complexity: O(n^2), n <= 1000
#include "supertrees.h"
#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; }
};
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: symmetric, diagonal 1, values in [0,3]
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] < 0 || p[i][j] > 3 || p[i][j] != p[j][i]){
cout<<0<<"\n";
return 0;
}
}
}
// If any 3 exists -> impossible per IOI analysis
for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(p[i][j] == 3){
cout<<0<<"\n";
return 0;
}
// DSU-A: components for p>0
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);
}
// collect nodes per component
unordered_map<int, vector<int>> compNodes;
for(int i=0;i<n;i++) compNodes[comp.find(i)].push_back(i);
// verify consistency: inside a component all pairs must have p>0
for(auto &pr : compNodes){
auto &vec = pr.second;
for(int a=0;a<(int)vec.size();a++){
for(int b=a+1;b<(int)vec.size();b++){
if(p[vec[a]][vec[b]] == 0){
cout<<0<<"\n";
return 0;
}
}
}
}
// Build adjacency matrix b (initially all zero)
vector<vector<int>> b(n, vector<int>(n,0));
// Process each component separately
for(auto &pr : compNodes){
const vector<int> nodes = pr.second;
if((int)nodes.size() == 1) continue; // single vertex, nothing to add
// DSU-B: inside component, groups where p==1 (these become trees attached to cycle nodes)
int m = nodes.size();
unordered_map<int,int> idx;
for(int i=0;i<m;i++) idx[nodes[i]] = i;
DSU group(m);
for(int i=0;i<m;i++){
for(int j=i+1;j<m;j++){
int u = nodes[i], v = nodes[j];
if(p[u][v] == 1) group.unite(i,j);
}
}
// collect groups
unordered_map<int, vector<int>> groups;
for(int i=0;i<m;i++) groups[group.find(i)].push_back(nodes[i]);
// verify: pairs within group must have p==1
for(auto &gpr : groups){
auto &gvec = gpr.second;
for(int a=0;a<(int)gvec.size();a++){
for(int b=a+1;b<(int)gvec.size();b++){
if(p[gvec[a]][gvec[b]] != 1){
cout<<0<<"\n";
return 0;
}
}
}
}
int groupsCount = (int)groups.size();
if(groupsCount == 1){
// pure tree on nodes: make a simple path
for(int i=0;i<m-1;i++){
int u = nodes[i], v = nodes[i+1];
b[u][v] = b[v][u] = 1;
}
continue;
}
// groupsCount >= 2: check cross-group pairs must be 2
// pick one representative per group
vector<int> reps;
reps.reserve(groupsCount);
for(auto &gpr : groups) reps.push_back(gpr.second[0]);
// check cross-group p values
for(int i=0;i<groupsCount;i++){
for(int j=i+1;j<groupsCount;j++){
int a = reps[i], c = reps[j];
if(p[a][c] != 2){
cout<<0<<"\n";
return 0;
}
}
}
// groupCount == 2 is impossible (would require a 2-cycle / parallel edges)
if(groupsCount == 2){
cout<<0<<"\n";
return 0;
}
// groupsCount >= 3: form a cycle on representatives
for(int i=0;i<groupsCount;i++){
int u = reps[i];
int v = reps[(i+1) % groupsCount];
b[u][v] = b[v][u] = 1;
}
// for each group, attach other nodes of the group to its representative by star edges
for(auto &gpr : groups){
int repnode = gpr.second[0];
for(size_t k=1;k<gpr.second.size();k++){
int v = gpr.second[k];
b[repnode][v] = b[v][repnode] = 1;
}
}
}
// All components processed successfully -> print adjacency
cout<<1<<"\n";
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(j) cout<<" ";
cout<<b[i][j];
}
cout<<"\n";
}
return 0;
}