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