QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#479884 | #996. 割点 | yzy1# | ML | 0ms | 0kb | C++23 | 2.0kb | 2024-07-15 21:31:52 | 2024-07-15 21:31:52 |
answer
#if defined(LOCAL)
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <bits/stdc++.h>
#if defined(LOCAL)
#define DBG_MACRO_NO_WARNING
#include <dbg.hpp>
#else
#define dbg(x...) (0)
#endif
using namespace std;
using ll = long long;
// #define int ll
#define rep(i, f, t) for (int i = (f), ed##i = (t); i <= ed##i; ++i)
#define re(i, t) rep (i, 1, t)
#define per(i, t, f) for (int i = (t), ed##i = (f); i >= ed##i; --i)
#define ste(i, f, t, s) for (int i = (f), ed##i = (t); i <= ed##i; i += s)
#define nxt(i, f, g) for (int i = g.h[f]; i; i = g.e[i].n)
#define umod(x) ((x) >= mo && ((x) -= mo))
#define dmod(x) ((x) < 0 && ((x) += mo))
#define y1 y1__
#define fio(x) (freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout))
template <class T, class E>
__attribute__((always_inline)) inline void up(T &x, E &&y) {
if (x < y) x = y;
}
template <class T, class E>
__attribute__((always_inline)) inline void down(T &x, E &&y) {
if (y < x) x = y;
}
const int N = 1e6 + 9;
struct G {
int tot = 1, h[N];
struct E {
int t, n;
} e[N << 1];
inline void Add(int f, int t) { e[++tot] = {t, h[f]}, h[f] = tot; }
} g;
int n, m, dfn[N], low[N], tim;
bool cut[N];
inline void Tar(int f, int eid) {
dfn[f] = low[f] = ++tim;
int son = 0;
nxt (i, f, g) {
if ((i >> 1) == eid) continue;
int t = g.e[i].t;
if (!dfn[i]) {
++son;
Tar(t, i >> 1);
if (eid && low[t] > dfn[f]) cut[f] = 1;
down(low[f], low[t]);
} else {
down(low[f], dfn[t]);
}
}
if (!eid && son >= 2) cut[f] = 1;
// dbg(f, dfn[f], low[f]);
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
re (i, m) {
int f, t;
cin >> f >> t;
g.Add(f, t), g.Add(t, f);
}
re (i, n)
if (!dfn[i]) Tar(i, 0);
int cnt = 0;
re (i, n)
if (cut[i]) ++cnt;
cout << cnt << '\n';
re (i, n)
if (cut[i]) cout << i << ' ';
cout << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
input:
12783 21968 4933 7832 8238 2739 3628 7841 9169 6390 7850 8797 8120 8710 5306 9807 10166 2063 2666 5157 5015 4651 4790 12586 10366 7137 12440 7218 6330 3670 2735 8492 1968 2750 6237 1112 6578 9221 743 3820 7155 4583 2537 9747 11331 9916 4454 5631 2978 10340 5293 1803 4944 4296 11800 2742 7903 2018 10...