이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Ignut
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 5;
const int MOD = 1e9 + 9;
int add(int a, int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int mult(int a, int b) {
return 1ll * a * b % MOD;
}
// ===================================================================== //
void build(vector<vector<int>> b);
struct DSU {
vector<int> p;
vector<vector<int>> comp;
void Init(int n) {
p.clear(), comp.clear();
for (int i = 0; i < n; i ++) p.push_back(i), comp.push_back({i});
}
int Get(int v) {
return p[v] == v ? v : p[v] = Get(p[v]);
}
void Unite(int u, int v) {
u = Get(u), v = Get(v);
if (u == v) return;
if (comp[u].size() > comp[v].size()) swap(u, v);
p[u] = v;
for (int val : comp[u]) comp[v].push_back(val);
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> b(n);
for (int i = 0; i < n; i ++) b[i].assign(n, 0);
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
if (p[i][j] == 3)
return 0;
}
}
// ================= chains =========================== //
bool have1[n] = {};
int h[n];
for (int i = 0; i < n; i ++) {
int hsh = 0;
int ppow = 1;
for (int j = 0; j < n; j ++) {
ppow = mult(ppow, P);
hsh = add(hsh, mult(ppow, p[i][j]));
have1[i] |= p[i][j] == 1;
}
h[i] = hsh;
}
DSU chains; chains.Init(n);
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
if (h[i] == h[j] && have1[i])
chains.Unite(i, j);
}
}
map<int, int> chain;
int nextChain = 1;
for (int i = 0; i < n; i ++) {
if (chains.Get(i) != i) continue;
if (chains.comp[i].size() == 1) continue;
for (int v : chains.comp[i]) chain[v] = nextChain;
nextChain ++;
for (int j = 0; j + 1 < chains.comp[i].size(); j ++) {
int u = chains.comp[i][j];
int v = chains.comp[i][j + 1];
b[u][v] = b[v][u] = true;
}
}
// ================== cycles ========================== //
DSU dsu; dsu.Init(n);
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
if (p[i][j] > 0) {
dsu.Unite(i, j);
}
}
}
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
bool f1 = (p[i][j] > 0);
bool f2 = (dsu.Get(i) == dsu.Get(j));
if (f1 != f2)
return 0;
}
}
for (int i = 0; i < n; i ++) {
if (dsu.Get(i) != i) continue;
// if (dsu.comp[i].size() == 1) continue;
// if (dsu.comp[i].size() <= 2)
// return 0;
// // cerr << dsu.comp[i].size() << '\n';
// for (int j = 0; j < dsu.comp[i].size(); j ++) {
// int u = dsu.comp[i][j], v = dsu.comp[i][(j + 1) % dsu.comp[i].size()];
// b[u][v] = b[v][u] = 1;
// }
map<int, int> usedChain;
vector<int> comp;
for (int v : dsu.comp[i]) {
if (!chain.count(v)) {
comp.push_back(v);
continue;
}
int ch = chain[v];
if (usedChain.count(ch)) {
continue;
}
usedChain[ch] ++;
comp.push_back(v);
}
if (comp.size() == 1)
continue;
if (comp.size() == 2)
return 0;
for (int j = 0; j < comp.size(); j ++) {
int u = comp[j];
int v = comp[(j + 1) % comp.size()];
b[u][v] = b[v][u] = true;
}
}
build(b);
return 1;
}
컴파일 시 표준 에러 (stderr) 메시지
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:81:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (int j = 0; j + 1 < chains.comp[i].size(); j ++) {
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:137:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for (int j = 0; j < comp.size(); j ++) {
| ~~^~~~~~~~~~~~~
# | 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... |