QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#341642#996. 割点MiniLong#WA 2ms7264kbC++143.1kb2024-02-29 20:16:342024-02-29 20:16:44

Judging History

你现在查看的是最新测评结果

  • [2024-02-29 20:16:44]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7264kb
  • [2024-02-29 20:16:34]
  • 提交

answer

#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; ++i)
#define _req(i, x, y) for(int i = x; i >= y; --i)
#define _rev(i, u) for(int i = head[u]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define mst(f, i) memset(f, i, sizeof f)
using namespace std;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
typedef long long ll;
typedef pair<int, int> PII;
namespace fastio{
    char ibuf[50007],*p1 = ibuf, *p2 = ibuf;
    #ifdef ONLINE_JUDGE
    #define get() p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 50007, stdin), p1 == p2) ? EOF : *p1++
    #else
    #define get() getchar()
    #endif
    template<typename T> inline void read(T &t){
        T x = 0, f = 1;
        char c = getchar();
        while(!isdigit(c)){
            if(c == '-') f = -f;
            c = getchar();
        }
        while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
        t = x * f;
    }
    template<typename T, typename ... Args> inline void read(T &t, Args&... args){
        read(t);
        read(args...);
    }
    template<typename T> void write(T t){
        if(t < 0) putchar('-'), t = -t;
        if(t >= 10) write(t / 10);
        putchar(t % 10 + '0');
    }
    template<typename T, typename ... Args> void write(T t, Args... args){
        write(t), putchar(' '), write(args...);
    }
    template<typename T> void writeln(T t){
        write(t);
        puts("");
    }
    template<typename T> void writes(T t){
        write(t), putchar(' ');
    }
    #undef get
};
using namespace fastio;
#define multitest() int T; read(T); _rep(tCase, 1, T)
namespace Calculation{
    const ll mod = 998244353;
    ll ksm(ll p, ll h){ll base = p % mod, res = 1; while(h){if(h & 1ll) res = res * base % mod; base = base * base % mod, h >>= 1ll;} return res;}
    void dec(ll &x, ll y){x = ((x - y) % mod + mod) % mod;}
    void add(ll &x, ll y){x = (x + y) % mod;}
    void mul(ll &x, ll y){x = x * y % mod;}
    ll sub(ll x, ll y){return ((x - y) % mod + mod) % mod;}
    ll pls(ll x, ll y){return ((x + y) % mod + mod) % mod;}
    ll mult(ll x, ll y){return x * y % mod;}
}
using namespace Calculation;
const int N = 1e5 + 5;
int n, m;
bool cut[N];
vector<int> G[N];
int id, dfn[N], low[N];
void tarjan(int u, int fa){
    dfn[u] = low[u] = ++id;
    int son = 0;
    for(auto &v : G[u]){
        if(!dfn[v]){
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] == dfn[v] && fa) cut[u] = 1;
            son++;
        }else if(v != fa) low[u] = min(low[u], dfn[v]);
    }
    // debug("u:%d low:%d dfn:%d\n", u, low[u], dfn[u]);
    if(!fa && son >= 2 || !fa && !son) cut[u] = 1;
}
int main(){
    read(n, m);
    _rep(i, 1, m){
        int u, v; read(u, v);
        G[u].pb(v), G[v].pb(u);
    }
    _rep(i, 1, n) if(!dfn[i]) tarjan(i, 0);
    int cnt = 0;
    _rep(i, 1, n) cnt += cut[i];
    writeln(cnt);
    _rep(i, 1, n) if(cut[i]) writes(i);
    puts("");
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 7264kb

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:

1859
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 1st numbers differ - expected: '1440', found: '1859'