이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<bool>> c(n, vector<bool>(n));
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
--x; --y;
c[x][y] = true;
c[y][x] = true;
g[x].push_back(y);
g[y].push_back(x);
}
const int N = 1005;
vector<vector<bitset<N>>> bs(n, vector<bitset<N>>(n));
for (int k = 0; k < n; k++) {
vector<bool> del(n);
del[k] = true;
for (int i : g[k]) {
del[i] = true;
}
vector<int> p(n);
iota(p.begin(), p.end(), 0);
vector<int> sz(n, 1);
function<int(int)> Root = [&](int x) {
return p[x] == x ? x : p[x] = Root(p[x]);
};
auto Merge = [&](int x, int y) {
x = Root(x);
y = Root(y);
if (x == y) {
return;
}
if (sz[x] < sz[y]) {
swap(x, y);
}
sz[x] += sz[y];
p[y] = x;
};
for (int i = 0; i < n; i++) {
if (del[i]) {
continue;
}
for (int j : g[i]) {
if (del[j]) {
continue;
}
Merge(i, j);
}
}
vector<bool> was(n);
for (int i = 0; i < n; i++) {
if (!del[i]) {
continue;
}
vector<int> xs;
for (int j : g[i]) {
if (del[j]) {
continue;
}
xs.push_back(Root(j));
if (!was[xs.back()]) {
was[xs.back()] = true;
bs[k][i][xs.back()] = 1;
}
}
for (int x : xs) {
was[x] = false;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (c[i][j]) {
continue;
}
for (int k : g[g[i].size() < g[j].size() ? i : j]) {
if (i == k || j == k || !c[i][k] || !c[j][k]) {
continue;
}
if ((bs[k][i] & bs[k][j]).count() == 0) {
continue;
}
vector<bool> del(n);
del[k] = true;
for (int p : g[k]) {
if (p != i && p != j) {
del[p] = true;
}
}
vector<int> p(n, -1);
vector<int> que(1, i);
vector<int> d(n, -1);
d[i] = 0;
for (int b = 0; b < (int) que.size(); b++) {
int i = que[b];
for (int j : g[i]) {
if (del[j]) {
continue;
}
if (d[j] == -1) {
p[j] = i;
d[j] = d[i] + 1;
que.push_back(j);
}
}
}
if (p[j] == -1) {
assert(false);
continue;
}
vector<int> seq;
for (int v = j; v != -1; v = p[v]) {
seq.push_back(v);
}
seq.push_back(k);
for (int i = 0; i < (int) seq.size(); i++) {
cout << seq[i] + 1 << " ";
}
cout << '\n';
return 0;
}
}
}
cout << "no" << '\n';
return 0;
}
# | 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... |
# | 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... |