# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
305320 | JustInCase | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 248 ms | 22264 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <vector>
#include <iostream>
#define int32_t int
#define int64_t long long
const int32_t MAX_N = 1000;
struct Dsu {
int32_t parent[MAX_N + 5], siz[MAX_N + 5];
void init(int32_t n) {
for(int32_t i = 0; i < n; i++) {
parent[i] = i;
siz[i] = 1;
}
}
void unite(int32_t x, int32_t y) {
if(siz[x] < siz[y]) {
parent[x] = y;
siz[y] += siz[x];
}
else {
parent[y] = x;
siz[x] += siz[y];
}
}
int32_t find_parent(int32_t x) {
if(parent[x] == x) {
return x;
}
parent[x] = find_parent(parent[x]);
return parent[x];
}
};
Dsu dsuLoops, dsuBranches;
int32_t construct(std::vector< std::vector< int32_t > > p) {
int32_t n = p.size();
dsuLoops.init(n);
dsuBranches.init(n);
for(int32_t i = 0; i < n; i++) {
for(int32_t j = i + 1; j < n; j++) {
if(p[i][j] == 3) {
return 0;
}
if(p[i][j] == 1) {
int32_t parI = dsuBranches.find_parent(i);
int32_t parJ = dsuBranches.find_parent(j);
if(parI != parJ) {
dsuBranches.unite(parI, parJ);
}
}
}
}
std::vector< std::vector< int32_t > > branches(n);
std::vector< int32_t > roots;
for(int32_t i = 0; i < n; i++) {
branches[dsuBranches.find_parent(i)].push_back(i);
}
std::vector< std::vector< int32_t > > res(n, std::vector< int32_t >(n, 0));
for(int32_t i = 0; i < n; i++) {
if(branches[i].size() > 0) {
roots.push_back(i);
for(int32_t j = 1; j < branches[i].size(); j++) {
res[branches[i][j - 1]][branches[i][j]] = res[branches[i][j]][branches[i][j - 1]] = 1;
}
}
}
for(int32_t i = 0; i < roots.size(); i++) {
for(int32_t j = i + 1; j < roots.size(); j++) {
if(p[roots[i]][roots[j]] == 2) {
int32_t parI = dsuLoops.find_parent(roots[i]);
int32_t parJ = dsuLoops.find_parent(roots[j]);
if(parI != parJ) {
dsuLoops.unite(parI, parJ);
}
}
}
}
std::vector< std::vector< int32_t > > loops(n);
for(int32_t i = 0; i < n; i++) {
int32_t par = dsuLoops.find_parent(i);
loops[par].push_back(i);
}
/**
for(int32_t i = 0; i < n; i++) {
std::cout << i << ": ";
for(auto &x : loops[i]) {
std::cout << x << " ";
}
std::cout << '\n';
}
*/
for(int32_t i = 0; i < n; i++) {
if(loops[i].size() == 2) {
return 0;
}
for(int32_t a = 0; a < loops[i].size(); a++) {
for(int32_t b = a + 1; b < loops[i].size(); b++) {
if(p[loops[i][a]][loops[i][b]] != 2) {
return 0;
}
}
}
if(loops[i].size() > 2) {
for(int32_t j = 0; j < loops[i].size() - 1; j++) {
res[loops[i][j]][loops[i][j + 1]] = res[loops[i][j + 1]][loops[i][j]] = 1;
}
res[loops[i][0]][loops[i].back()] = res[loops[i].back()][loops[i][0]] = 1;
}
}
build(res);
return 1;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |