| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 302698 | JooDdae | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// void build(vector<vector<int>> v){
// for(auto x : v){
// for(int y : x) printf("%d ",y);
// printf("\n");
// }
// }
int par[1000];
vector<int> v[1000];
int find(int a){
if(a == par[a]) return a;
return par[a] = find(par[a]);
}
void merge(int a, int b){
a = find(a), b = find(b);
par[a] = b;
}
int construct(vector<vector<int>> p){
int n = p.size();
vector<vector<int>> ans(n, vector<int>(n));
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(p[i][j] == 3) return 0;
for(int i=0;i<n;i++) par[i] = i;
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(p[i][j] == 1) merge(i, j);
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(p[i][j] != 1 && find(i) == find(j)) return 0;
for(int i=0;i<n;i++) v[find(i)].push_back(i);
for(int i=0;i<n;i++) if(v[i].size() > 1){
for(int j=0;j<v[i].size()-1;j++){
for(int k=0;k<n;k++){
if(k != v[i][j] && k != v[i][j+1] && p[v[i][j]][k] != p[v[i][j+1]][k]) return 0;
}
ans[v[i][j]][v[i][j+1]] = ans[v[i][j+1]][v[i][j]] = 1;
}
}
vector<int> v2;
for(int i=0;i<n;i++) if(v[i].size()) v2.push_back(v[i][0]);
for(int i=0;i<v2.size();i++) par[i] = i, v[i].clear();
for(int i=0;i<v2.size();i++) for(int j=i+1;j<v2.size();j++) if(p[v2[i]][v2[j]] == 2) merge(i, j);
for(int i=0;i<v2.size();i++) v[find(i)].push_back(v2[i]);
for(int i=0;i<v2.size();i++) if(v[i].size() > 1){
if(v[i].size() == 2) return 0;
int sz = v[i].size();
for(int j=0;j<v[i].size();j++){
for(int k=0;k<v[i].size();k++){
if(j != k && (j+1)%sz != k && (p[v[i][j]][v[i][k]] == 2) != (p[v[i][(j+1)%sz]][v[i][k]] == 2)) return 0;
}
ans[v[i][j]][v[i][(j+1)%sz]] = ans[v[i][(j+1)%sz]][v[i][j]] = 1;
}
}
build(ans);
return 1;
}
// int main(){
// int n; scanf("%d",&n);
// vector<vector<int>> v(n, vector<int>(n));
// for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&v[i][j]);
// printf("%d\n",construct(v));
// }