This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
const int N = 1005;
vector<vector<bool>> c(n, vector<bool>(n));
vector<bitset<N>> cb(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);
cb[x][y] = 1;
cb[y][x] = 1;
}
auto Solve = [&](int i, int j, int k) {
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);
}
}
}
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';
};
mt19937 rng(time(0));
vector<int> order(n);
iota(order.begin(), order.end(), 0);
shuffle(order.begin(), order.end(), rng);
for (int k : order) {
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<vector<int>> ids(n);
for (int i = 0; i < n; i++) {
if (!c[i][k]) {
continue;
}
for (int j : g[i]) {
if (del[j]) {
continue;
}
ids[Root(j)].push_back(i);
}
}
for (int i = 0; i < n; i++) {
sort(ids[i].begin(), ids[i].end());
ids[i].erase(unique(ids[i].begin(), ids[i].end()), ids[i].end());
sort(ids[i].begin(), ids[i].end(), [&](int i, int j) {
return (int) g[i].size() > (int) g[j].size();
});
int sz = (int) ids[i].size();
if ((int) ids[i].size() >= 100) {
bitset<N> bs;
bool found = false;
for (int x = 0; x < sz; x++) {
if ((cb[ids[i][x]] & bs) != bs) {
found = true;
break;
}
bs[ids[i][x]] = 1;
}
if (!found) {
continue;
}
}
for (int x = 0; x < sz; x++) {
for (int y = x + 1; y < sz; y++) {
if (!c[ids[i][x]][ids[i][y]]) {
Solve(ids[i][x], ids[i][y], k);
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... |