| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 309047 | tjdgus4384 | 슈퍼트리 잇기 (IOI20_supertrees) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
vector<int> graph[1001], trees[1001];
vector<vector<int> > b, P, newp;
vector<int> v[1001];
vector<int> sametree;
bool visited[1001];
void dfs(int x, int cnt){
graph[cnt].push_back(x);
for(int i = 0;i < v[x].size();i++){
if(visited[v[x][i]]) continue;
visited[v[x][i]] = true;
dfs(v[x][i], cnt);
}
}
void make_tree(int x){
for(int i = 0;i < v[x].size();i++){
if(visited[v[x][i]]) continue;
if(P[x][v[x][i]] != 1) continue;
visited[v[x][i]] = true;
sametree.push_back(v[x][i]);
make_tree(v[x][i]);
b[x][v[x][i]] = 1;
b[v[x][i]][x] = 1;
}
}
void build(vector<vector<int> > b){
for(int i = 0;i < b.size();i++){
for(int j = 0;j < b.size();j++){
printf("%d ", b[i][j]);
}
printf("\n");
}
}
int construct(vector<vector<int> > p){
P = p;
b.resize(p.size());
newp.resize(p.size());
for(int i = 0;i < p.size();i++){
b[i].resize(p.size());
newp[i].resize(p.size());
for(int j = 0;j < p.size();j++){
if(i == j) continue;
if(p[i][j]) v[i].push_back(j);
if(p[i][j] == 3) return 0;
}
}
int cnt = 0;
for(int i = 0;i < p.size();i++){
if(visited[i]) continue;
visited[i] = true;
dfs(i, cnt); cnt++;
}
for(int i = 0;i < p.size();i++) visited[i] = false;
for(int i = 0;i < cnt;i++){
vector<int> nv;
for(int j = 0;j < graph[i].size();j++){
if(visited[graph[i][j]]) continue;
visited[graph[i][j]] = true;
sametree.push_back(graph[i][j]);
make_tree(graph[i][j]);
for(int x1 = 0;x1 < sametree.size();x1++){
for(int x2 = 0;x2 < sametree.size();x2++){
if(x1 == x2) continue;
newp[sametree[x1]][sametree[x2]] = newp[sametree[x2]][sametree[x1]] = 1;
}
}
sametree.clear();
nv.push_back(graph[i][j]);
}
if(nv.size() <= 1) continue;
if(nv.size() <= 2) return 0;
for(int j = 0;j < nv.size() - 1;j++){
b[nv[j]][nv[j+1]] = 1;
b[nv[j+1]][nv[j]] = 1;
}
for(int x1 = 0;x1 < nv.size();x1++){
for(int x2 = 0;x2 < graph[i].size();x2++){
if(nv[x1] == graph[i][x2]) continue;
if(newp[nv[x1]][graph[i][x2]]) continue;
newp[nv[x1]][graph[i][x2]] = newp[graph[i][x2]][nv[x1]] = 2;
}
}
for(int x1 = 0;x1 < graph[i].size();x1++){
for(int x2 = 0;x2 < graph[i].size();x2++){
if(graph[i][x1] == graph[i][x2]) continue;
if(newp[graph[i][x1]][graph[i][x2]]) continue;
newp[graph[i][x1]][graph[i][x2]] = newp[graph[i][x2]][graph[i][x1]] = 2;
}
}
b[nv[0]][nv.back()] = 1;
b[nv.back()][nv[0]] = 1;
}
for(int i = 0;i < p.size();i++){
for(int j = 0;j < p.size();j++){
if(i == j) continue;
if(p[i][j] != newp[i][j]) return 0;
}
}
build(b);
return 1;
}