QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#480640 | #996. 割点 | Froranzen# | WA | 0ms | 10600kb | C++17 | 6.6kb | 2024-07-16 17:03:52 | 2024-07-16 17:03:53 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, f, t) for(int i(f); i <= t; ++i)
#define re(i, t) for(int i(1); i <= t; ++i)
#define per(i, t, f) for(int i(t); i >= f; --i)
#define pe(i, t) for(int i(t); i >= 1; --i)
#define nx(i, u) for(int i(head[u]); i; i = e[i].nxt)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair <int, int> pii;
#define pb push_back
#define fi first
#define i128 __int128
#define se second
#define Ls (ix(l, mid))
#define Rs (ix(mid+1, r))
#define ix(l, r) ((l + r) | (l != r))
#define mp(i, j) (make_pair(i, j))
//#define int long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
struct IO {
#define MAXSIZE 1<<21
#define isdigit(x) (x >= '0' && x <= '9')
#define isspace(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
char ibuf[MAXSIZE], obuf[MAXSIZE], *s1, *s2, *s3, endl, blank;
int round[10] = {0, 0, 0, 0, 0, 1, 1, 1, 1}, sta[65], precisions;
bool fail;
FILE *in_stream, *out_stream;
IO(FILE *_stream = stdin, FILE *__stream = stdout) { reset(_stream,__stream); }
#if DEBUG
#else
~IO() {close();}
#endif
inline void reset (FILE *_stream = stdin, FILE *__stream = stdout, bool reset = true) {
s1 = s3 = ibuf, s2 = obuf, in_stream = _stream, out_stream = __stream, fail = false;
if(reset) { endl = '\n'; blank = ' '; precisions = 6; }
}
inline void flush_in() {s3 = (s1 = ibuf) + fread(ibuf, 1, MAXSIZE, in_stream); }
inline void flush_out() { fwrite(obuf, 1, s2-obuf, out_stream), s2 = obuf; }
inline void flush_out_with_stream() { flush_out(); fflush(out_stream); }
inline char get() {
#if DEBUG
return getchar();
#endif
return s1 == s3 && (flush_in(), fail = s1 == s3) ? 0 : *s1++;
}
inline void put(char ch) {
#if DEBUG
putchar(ch);
#else
s2-obuf == MAXSIZE ? flush_out(), 0 : 0, *s2++=ch;
#endif
}
template <class T>
inline void read(T &x) {
bool sign = false; char c = get(); x = 0;
while(!isdigit(c) && c) {sign=c=='-'; c = get(); }
while(isdigit(c)) { x = (x<<1) + (x<<3) + (c^'0'); c = get(); }
sign ? x = ~x+1 : 0;
}
inline void read(double &x) {
bool sign = false; char c = get(); x = 0;
while(!isdigit(c) && c) { sign=c=='-'; c = get(); }
while(isdigit(c)) { x = x * 10 + (c^'0'); c = get(); }
if(c=='.') { c = get(); double tmp = 1; while(isdigit(c)) { tmp /= 10, x += tmp * (c^'0'); c = get(); } }
sign ? x = -x : 0;
}
inline void read(long double &x) {
bool sign = false; register char c = get(); x = 0;
while(!isdigit(c) && c) { sign=c=='-'; c = get(); }
while(isdigit(c)) { x = x * 10 + (c^'0'); c = get(); }
if(c == '.') { c = get(); register long double tmp = 1; while(isdigit(c)) { tmp /= 10, x += tmp * (c^'0'); c = get(); } }
sign ? x = -x : 0;
}
inline void read(char *s) {
char c = get();
while(isspace(c)) c = get();
while(!isspace(c) && c) { *s++=c; c = get(); }
*s = '\0';
}
inline void read(char &c) {
do
c = get();
while(isspace(c));
}
template <class T, class ...Args>
inline void read(T &x, Args &...args) { read(x), read(args...); }
template <class T>
inline void write(T x) {
int top = 0;
if(x<0) { put('-'); sta[top++] = ~(x%10)+1, x /= 10; x = ~x+1; }
else sta[top++] = x%10, x /= 10;
while(x) sta[top++] = x%10 ,x /= 10;
while(top) put(sta[--top]^'0');
}
inline void write(double y) {
int top = 0;
if(y<0) { put('-'); y=-y; }
int x = y; y -=x;
write(x);
if(y) {
do
sta[top++] = y*10, y = y*10 - sta[top-1];
while(top<precisions-1);
sta[top++] = y*10 + round[(int)((y*10-((int)(y*10)))*10)];
}
put('.');
for(int i(0); i<top; ++i) put(sta[i]^'0');
for(int i(top); i<precisions; ++i) put('0');
}
inline void write(long double y) {
register int top = 0;
if(y<0) { put('-'); y=-y; }
int x = y; y -= x;
write(x);
if(y) {
do
sta[top++] = y*10, y = y*10 - sta[top-1];
while(top<precisions-1);
sta[top++] = y*10 + round[(int)((y*10-((int)(y*10)))*10)];
}
put('.');
for(register int i(0); i < top; ++i) put(sta[i]^'0');
for(register int i(top); i < precisions; ++i) put('0');
}
inline void write(const char ch) { put(ch); }
inline void write(char *s) { while(*s!='\0') put(*s++); }
inline void write(const char *s) { while(*s!='\0') put(*s++); }
inline void write(const std::string str) { write(str.c_str()); }
inline IO &precision(const int x) { precisions=x; return *this; }
template <class T,class ...Args>
inline void write(T x,Args ...args) { write(x), blank?put(blank), 0:0, write(args...); }
template <class ...Args>
inline void writeln(Args ...args) { write(args...), endl?put(endl), 0:0; }
template <class T>
inline IO &operator>>(T &x) { read(x); return *this; }
inline IO &operator>>(IO &x) { return *this; }
template <class T>
inline IO &operator<<(const T x) { write(x); return *this; }
inline IO &operator<<(IO &x) { return *this; }
inline operator bool() { return !fail; }
template <class T>
inline operator T() { T x; read(x); return x; }
inline void open(FILE *_stream=stdin,FILE *__stream=stdout) { close(), reset(_stream, __stream, false); }
inline void close() { flush_out_with_stream(); fclose(in_stream), fclose(out_stream); }
#define read(x) io>>x
#define out(x) io<<x
}io;
const int N = 1e5 + 5;
int n, m, u, v;
struct node {
int to, nxt;
}e[N<<4];
int b[N<<4];
int head[N], cnt = 1;
void add (int u, int v) {
e[++cnt] = (node){v, head[u]};
head[u] = cnt;
}
int dfn[N], low[N], tnt;
void tarjan (int u, int fa) {
dfn[u] = low[u] = ++tnt;
nx(i, u) {
int v = e[i].to;
if(v == fa) continue;
if(!dfn[v]) {
tarjan(v, u);
if(low[v] >= dfn[u]) {
++b[u];
}
low[u] = min(low[u], low[v]);
}
else low[u] = min(low[u], dfn[v]);
}
}
int main () {
io >> n >> m;
re(i, m) {
io >> u >> v;
add(u, v), add(v, u);
}
re(i, n) {
if(!dfn[i]) tarjan(i, 0), --b[i];
}
int lc = 0;
re(i, n) {
lc += (b[i] > 0);
}
io << lc << "\n";
re(i, n) {
if(b[i]) io << i << " ";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 10600kb
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...
output:
1440 13 14 22 26 27 29 33 35 36 37 39 45 47 53 62 78 91 112 116 118 119 127 131 132 144 151 155 156 163 166 168 177 183 187 192 194 196 205 219 220 223 225 239 248 250 254 256 265 285 290 293 313 315 318 319 336 337 338 347 356 358 371 376 386 388 408 414 415 427 446 459 461 464 471 477 486 504 513 ...
result:
wrong answer 3rd numbers differ - expected: '22', found: '14'