QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#189370 | #5201. Cactus Meets Torus | ckiseki | WA | 1ms | 3528kb | C++20 | 3.7kb | 2023-09-27 13:42:54 | 2023-09-27 13:42:56 |
Judging History
answer
// An AC a day keeps the doctor away.
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(args...) qqbx(#args, args)
#define orange(args...) danb(#args, args)
using std::cerr;
template <typename ...T> void qqbx(const char *s, T ...args) {
int cnt = sizeof...(T);
((cerr << "\e[1;32m(" << s << ") = ("), ..., (cerr << args << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I> void danb(const char *s, I L, I R) {
cerr << "\e[1;32m[ " << s << " ] = [ ";
for (int f = 0; L != R; ++L) cerr << (f++ ? ", " : "") << *L;
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)
using namespace std;
struct RST {
int n; vector<vector<int>> T;
RST(auto &G) : n(G.size()), T(n) {
vector<int> stk, vis(n), low(n);
auto dfs = [&](auto self, int u, int d) -> void {
low[u] = vis[u] = d; stk.push_back(u);
for (int v : G[u]) if (!vis[v]) {
self(self, v, d + 1);
if (low[v] == vis[u]) {
int cnt = T.size(); T.emplace_back();
for (int x = -1; x != v; stk.pop_back())
T[cnt].push_back(x = stk.back());
T[u].push_back(cnt);
} else low[u] = min(low[u], low[v]);
} else low[u] = min(low[u], vis[v]);
};
dfs(dfs, 0, 1);
}
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
while (cin >> n >> m && n && m) {
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
int k;
cin >> k;
vector<int> p(k);
for (int &x: p) cin >> x, --x;
for (int j = 1; j < k; j++) {
int a = p[j - 1], b = p[j];
g[a].emplace_back(b);
g[b].emplace_back(a);
}
}
RST tr(g);
vector<int> bcc(tr.T.size());
int k = 0;
for (size_t i = n; i < tr.T.size(); i++) {
if (tr.T[i].size() + 1 >= 3) {
bcc[i] = true;
++k;
}
}
if (k == 0) {
cout << "Yes\n";
continue;
}
vector<vector<int>> nt(tr.T.size());
for (size_t i = 0; i < tr.T.size(); i++) {
for (int j: tr.T[i]) {
cerr << i << ' ' << j << endl;
}
}
vector<int> cnt(tr.T.size());
const auto dfs = [&](auto self, int i) -> void {
cnt[i] = bcc[i];
for (int j: tr.T[i]) {
self(self, j);
if (cnt[j] != 0 && cnt[j] != k) {
nt[i].emplace_back(j);
nt[j].emplace_back(i);
}
cnt[i] += cnt[j];
}
};
dfs(dfs, 0);
int root = -1;
for (size_t i = n; i < tr.T.size(); i++)
if (bcc[i] && nt[i].size() == 1) {
root = i;
break;
}
assert (root != -1);
int dfc = 0;
vector<int> tin(tr.T.size()), tou(tr.T.size());
vector<int> pa(tr.T.size());
const auto dfs2 = [&](auto self, int i, int f) -> void {
pa[i] = f;
tin[i] = dfc++;
for (int j: nt[i]) {
if (j == f) continue;
self(self, j, i);
}
tou[i] = dfc;
};
dfs2(dfs2, root, -1);
vector<int> z;
for (size_t i = n; i < tr.T.size(); i++)
if (bcc[i]) {
int x = i;
if (pa[x] != -1) x = pa[x];
if (pa[x] != -1) x = pa[x];
z.push_back(x);
}
sort(z.begin(), z.end(), [&](int a, int b) { return tin[a] < tin[b]; });
bool ok = true;
for (size_t i = 1; i < z.size(); i++) {
int x = z[i - 1];
int y = z[i];
ok &= tin[x] <= tin[y] && tin[y] < tou[x];
}
if (ok) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3472kb
input:
6 1 8 1 2 3 1 4 5 6 4 10 2 9 1 2 3 1 10 4 5 6 4 5 7 8 9 7 10 0 0
output:
Yes No
result:
ok 2 token(s): yes count is 1, no count is 1
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3528kb
input:
15 3 9 1 2 3 4 5 6 7 8 3 7 2 9 10 11 12 13 10 5 2 14 9 15 10 15 7 3 1 2 3 3 4 2 5 3 6 2 7 3 8 2 9 3 10 2 11 3 12 2 13 3 14 2 15 1 0 2 1 2 1 2 2 1 2 2 1 3 1 4 1 3 2 1 4 2 3 1 2 3 2 2 4 6 2 5 1 2 3 4 5 2 4 6 7 3 5 1 2 3 4 5 2 4 6 2 4 7 7 2 6 1 2 3 4 5 6 2 5 7 8 3 6 1 2 3 4 5 6 2 5 7 2 5 8 9 4 5 1 2 3 ...
output:
Yes Yes
result:
wrong answer Answer contains longer sequence [length = 18], but output contains 2 elements