| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 405063 | ly20 | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1123;
int comp[MAXN];
vector <int> grafo[MAXN];
int marc[MAXN];
int cmp;
//vector <int> grafo2[MAXN];
void dfs(int v) {
marc[v] = 1;
comp[v] = cmp;
for(int i = 0; i < grafo[v].size(); i++) {
int viz = grafo[v][i];
if(marc[viz] == 1) continue;
dfs(viz);
}
}
int resp[MAXN][MAXN];
int rep[MAXN];
int cic[MAXN][MAXN];
int rep[MAXN];
int cm2[MAXN], cmp2;
int marc2[MAXN];
vector <int> ln[MAXN];
vector <vector <int> > answer;
//vector <int> temp;
void dfs2(int v) {
marc2[v] = 1;
cm2[v] = cmp2;
for(int i = 0; i < cmp; i++) {
if(marc[i] == 1) continue;
if(cic[v][i] == 1) dfs2(i);
}
}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> answer;
for(int i = 0; i < n; i++) {
comp[i] = i;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(p[i][j] == 1) {
grafo[i].push_back(j);
}
}
}
for(int i = 0; i < n; i++) {
if(marc[i] == 0) {
dfs(i);
cmp++;
}
}
for(int i = 0; i < cmp; i++) {
for(int j = 0; j < n; j++) if(comp[j] == i) ln[i].push_back(j);
int m = ln[i].size();
for(int j = 0; j < m; j++) {
int cur = ln[i][j];
for(int k = j + 1; k < m; k++) {
int tst = ln[i][k];
if(p[cur][tst] != 1) {
return 0;
}
}
}
for(int j = 0; j < m - 1; j++) {
int pr = j + 1;
resp[ln[i][j]][ln[i][pr]] = 1;
resp[ln[i][pr]][ln[i][j]] = 1;
}
rep[i] = ln[i][0];
}
for(int i = 0; i < cmp; i++) {
for(int j = i + 1; j < cmp; j++) {
int bs = p[rep[i]][rep[j]];
for(int k = 0; k < ln[i].size(); k++) {
for(int l = 0; l < ln[j].size(); l++) {
if(p[ln[i][k]][ln[j][l]] != bs) bs = -1;
}
}
if(bs == 1) {
cic[i][j] = 1;
cic[j][i] = 1;
}
else if (bs == 0)
else return 0;
}
}
for(int i = 0; i < cmp; i++) {
if(marc2[i] == 0) {
dfs2(i);
cmp2++;
}
}
for(int i = 0; i < cmp2; i++) {
vector <int> temp;
for(int j = 0; j < cmp; j++) if(cm2[j] == i) temp.push_back(j);
int m = temp.size();
for(int j = 0; j < m; j++) {
for(int k = j + 1; k < m; k++) {
if(cic[temp[j]][temp[k]] == 0) return 0;
}
}
if(temp.size() == 1) continue;
for(int j = 0; j < m; j++) {
int pr = (j + 1) % m;
resp[rep[temp[pr]]][rep[temp[j]]] = 1;
resp[rep[temp[j]]][rep[temp[pr]]] = 1;
}
}
for (int i = 0; i < n; i++) {
vector<int> row;
for(int j = 0; j < n; j++) {
row.push_back(resp[i][j]);
}
answer.push_back(row);
}
build(answer);
return 1;
}