| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 667101 | atigun | Connecting Supertrees (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct dsu{
vector<int> parent, size;
int N;
void assign(int dsusize){
N = dsusize;
parent.assign(N, 0);
iota(parent.begin(), parent.end(), 0);
size.assign(N, 1);
}
int find(int v){
return parent[v] = (parent[v] == v ? v : find(parent[v]));
}
void merge(int v, int u){
if(find(v) == find(u))
return;
if(size[find(v)] < size[find(u)])
swap(u, v);
size[find(v)]+= size[find(u)];
parent[find(u)] = parent[find(v)];
}
bool is_same(int v, int u){
return (find(v) == find(u));
}
};
int N;
vector<vector<int>> p;
dsu DSU;
vector<vector<int>> ans;
void build(vector<vector<int>>& b){
int n = b.size();
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cout << b[i][j] << " ";
}
cout << "\n";
}
}
void make_edge(int x, int y){
cout << x << " " << y << "\n";
ans[x][y] = ans[y][x] = 1;
}
int construct(vector<vector<int>> p){
int n = p.size();
ans.assign(n, vector<int>(n));
DSU.assign(n);
bool ok = 1;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
ok&= (p[i][j] == p[j][i]);
if(p[i][j])
DSU.merge(i, j);
}
ok&= (p[i][i] == 1);
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
ok&= (DSU.is_same(i, j) == (p[i][j] != 0));
if(!ok)
return 0;
vector<vector<int>> groups(n);
for(int i = 0; i < n; i++)
groups[DSU.find(i)].push_back(i);
for(vector<int> &G : groups){
if((int) (G.size()) <= 1)
continue;
vector<int> all_two, is_two(n, 1);
all_two.reserve(n);
for(int I : G){
for(int J : G)
is_two[I]&= (I == J || p[I][J] == 2);
if(is_two[I])
all_two.push_back(I);
}
vector<int> color(n, -1);
color[G[0]] = 0;
for(int i = 0; i < (int) (G.size()); i++){
if(is_two[G[i]])
continue;
for(int j = i+1; j < (int) (G.size()); j++){
if(is_two[G[j]])
continue;
if(p[G[i]][G[j]] == 1){
ok&= (color[G[j]] == -1 || color[G[j]] == color[G[i]]);
color[G[j]] = color[G[i]];
} else if(p[G[i]][G[j]] == 2){
ok&= (color[G[j]] == -1 || color[G[j]] == (color[G[i]]^1));
color[G[j]] = color[G[i]]^1;
}
}
}
if(!ok)
break;
vector<vector<int>> side(2);
for(int I : G){
if(is_two[I] || color[I] == -1)
continue;
side[color[I]].push_back(I);
}
for(int i = 1; i < (int) (all_two.size()); i++)
make_edge(all_two[i-1], all_two[i]);
for(int i = 1; i < (int) (side[0].size()); i++)
make_edge(side[0][i-1], side[0][i]);
for(int i = 1; i < (int) (side[1].size()); i++)
make_edge(side[1][i-1], side[1][i]);
if(all_two.size()){
if(side[0].size() && (int) (side[1].size())){
make_edge(side[0].back(), side[1][0]);
make_edge(side[0].back(), all_two[0]);
make_edge(side[1][0], all_two.back());
} else if((int) (side[0].size()) && side[1].empty()){
ok&= ((int) (all_two.size()) >= 2);
ok&= ((int) (side[0].size()) >= 1);
make_edge(side[0].back(), all_two[0]);
make_edge(side[0].back(), all_two.back());
} else if(side[0].empty() && (int) (side[1].size())){
ok&= ((int) (all_two.size()) >= 2);
ok&= ((int) (side[1].size()) >= 1);
make_edge(side[0][0], all_two.back());
make_edge(side[0][0], all_two[0]);
} else if(side[0].empty() && side[1].empty()){
ok&= ((int) (all_two.size()) >= 2);
make_edge(all_two[0], all_two.back());
}
} else{
ok&= (side[1].empty());
}
}
if(!ok)
return 0;
build(ans);
return 1;
}
void solve(){
int n;
cin >> n;
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];
cout << construct(p) << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int tt = 1;
// cin >> tt;
while(tt--){
solve();
}
}