QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#502751#996. 割点gogo11WA 15ms7616kbC++203.0kb2024-08-03 13:12:522024-08-03 13:12:53

Judging History

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

  • [2024-08-03 13:12:53]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:7616kb
  • [2024-08-03 13:12:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define all(x) x.begin(),x.end()
constexpr int N = 2e4 + 10;
constexpr int M = 5e5 + 10;
constexpr ll Mod = 998244353;
constexpr int INF = 0x3f3f3f3f;
constexpr ll Base = 1277;
constexpr int MAXBIT = 30;
int root;
bool cut_point[N],bridge[M];;
struct EBCC {
    int n;
    vector<vector<pair<int,int>>> adj;
    vector<int> stk;
    vector<int> dfn,low,col;
    int cur,cnt,edgeid,points,edges;
    EBCC() {}
    EBCC(int n) {init(n);}
    void init(int n) {
        this->n=n;
        adj.assign(n+1,{});
        dfn.assign(n+1,-1);
        low.resize(n+1);
        col.assign(n+1,-1);
        stk.clear();
        cur=cnt=edgeid=points=edges=0;
    }
    void addEdge(int u,int v) {
        adj[u].push_back({v,edgeid++});
        adj[v].push_back({u,edgeid++});
    }
    void dfs(int x,int inedge) {
        int tot=0;
        dfn[x]=low[x]=cur++;
        stk.push_back(x);
        for(auto [y,id] : adj[x]) {
            if(id==(inedge^1)) continue;
            if(dfn[y]==-1) {
                dfs(y,id);
                ++tot;
                low[x]=min(low[x],low[y]);
                if(low[y]>dfn[x] && !bridge[id/2])
                {
                    edges+=1;
                    bridge[id/2]=1;
                }
                if(low[y]>dfn[x] && !cut_point[x])
                {
                    points+=1;
                    cut_point[x]=true;
                }
            }else if(col[y]==-1 && dfn[y]<dfn[x]) {
                low[x]=min(low[x],dfn[y]);
            }
        }
        if(x==root && tot<2 && cut_point[x])
        {
            points-=1;
            cut_point[x]=false;
        }
        if(dfn[x]==low[x]) {
            int y;
            cnt+=1;
            do{
                y=stk.back();
                col[y]=cnt;
                stk.pop_back();
            } while(y!=x);

        }
    }
    vector<int> work() {
        for(int i=1;i<=n;i++)
            if(dfn[i]==-1)
            {
                root=i;
                dfs(i,-1);
            }
        return col;
    }
    int ebccnum() {
        return cnt;
    }
    int cut_points() {
        return points;
    }
    int cut_edges() {
        return edges;
    }
};
void solve()
{
    int n,m;
    cin>>n>>m;
    EBCC ebcc(n);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        ebcc.addEdge(u,v);
    }
    ebcc.work();
    cout<<ebcc.cut_points()<<"\n";
    for(int i=1;i<=n;i++)
        if(cut_point[i])
            cout<<i<<"\n";
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // #endif
    int _ = 1;
    // cin >> _;
    while (_--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 5412kb

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
22
26
27
29
33
35
37
39
45
47
53
62
78
91
118
127
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
313
315
337
338
347
356
358
376
386
388
408
414
415
427
446
459
461
464
477
486
504
513
519
538
555
557
571
574
608
611
619
625
626
63...

result:

ok 1441 numbers

Test #2:

score: 0
Accepted
time: 15ms
memory: 7616kb

input:

18363 71341
1605 8881
5063 10231
7404 17473
10255 9479
16324 3467
15801 1736
665 11785
10719 12186
2819 13697
11362 11499
9368 8580
3518 1960
7119 8384
675 14139
4860 13564
7360 12510
13835 873
12205 6638
10193 13179
12015 13640
10810 11671
2454 7181
703 403
2416 8623
12694 18083
7377 5420
9179 2689...

output:

47
4
1376
1552
2495
3741
3819
5195
5850
5993
6098
6573
6584
6751
7404
7681
7915
7956
8352
8729
8777
9228
9897
10643
10736
12393
12474
12839
13087
13241
13701
13747
14039
14099
14397
14448
14586
14590
16005
16431
16716
16849
17014
17165
17832
18062
18064
18328

result:

ok 48 numbers

Test #3:

score: 0
Accepted
time: 12ms
memory: 6928kb

input:

15902 58199
14048 2132
168 14936
419 3928
840 522
12105 9088
9688 4240
7385 10268
7103 2533
15533 2640
1883 4262
5174 252
10602 5942
13411 2659
704 9029
8368 14765
3068 472
13500 1924
5402 375
6312 8408
4636 14068
14471 13367
8748 2243
649 15653
14319 14458
3053 10330
10183 9599
2587 9274
1257 5543
...

output:

75
179
401
459
725
1104
1263
1264
1351
1381
1418
1501
1905
2043
2425
2606
2817
2893
2906
2939
3141
3246
3277
3278
3900
4077
4274
4559
4691
5022
5024
5592
5836
6090
6918
7294
7310
7536
8281
8329
8386
8699
9378
9523
9659
9860
9942
9974
10149
10174
10318
10337
10389
10408
10636
10832
10965
11002
11150
...

result:

ok 76 numbers

Test #4:

score: 0
Accepted
time: 6ms
memory: 5568kb

input:

18729 22691
1526 8120
5080 15113
10543 5242
469 13542
15687 330
6428 10849
18518 14145
7891 13098
11933 15334
18270 10333
9520 5553
9910 9989
16942 9998
8595 6975
7648 7373
16304 17530
4955 13223
439 6627
6290 5937
16919 8156
7122 1855
4534 17878
2027 2654
15427 11079
2980 2014
16983 12978
13608 116...

output:

4294
3
10
13
15
16
31
34
35
36
39
44
50
51
56
60
61
64
68
70
73
77
101
106
108
109
112
113
116
135
145
153
154
156
161
168
169
171
175
182
189
195
202
204
206
210
212
215
216
225
228
230
231
233
239
240
252
255
257
259
263
267
268
278
280
281
282
284
287
288
289
290
293
296
298
299
300
303
304
307
3...

result:

ok 4295 numbers

Test #5:

score: 0
Accepted
time: 10ms
memory: 6484kb

input:

16373 44886
12965 1206
12094 2782
2636 13078
15085 3335
10744 10210
15785 9865
4495 2037
9706 4255
5772 245
5678 6452
11283 1887
9153 6742
13368 6183
2490 6469
13089 3280
13210 8098
1518 3803
13957 2313
7625 15047
7060 9827
602 11269
1391 6385
9763 9916
1158 2644
5060 9521
8609 12859
1831 9547
3096 ...

output:

349
138
154
211
242
352
391
441
448
508
647
715
730
751
775
867
884
902
1043
1135
1163
1248
1371
1400
1475
1552
1554
1588
1644
1657
1662
1665
1702
1731
1744
1872
1975
1988
2049
2094
2133
2137
2173
2337
2360
2439
2580
2657
2771
2787
2792
2799
2811
2824
2854
2883
2891
2894
2908
2945
2958
2966
3018
305...

result:

ok 350 numbers

Test #6:

score: 0
Accepted
time: 11ms
memory: 6896kb

input:

15138 55007
8803 12908
10265 469
6987 507
5087 13680
5014 5860
12365 12685
11981 4843
5206 14604
9244 14292
10112 417
12950 6428
6329 3140
8601 5311
8936 10274
13027 6570
11261 6150
2681 14871
13629 10089
7382 11059
6178 228
7870 6080
5166 7622
3136 7552
2089 1245
11538 1301
9243 13742
8373 1737
114...

output:

93
10
319
408
491
592
622
767
1086
1217
1465
1591
1714
1725
1845
1880
2923
2938
3140
3143
3176
3236
3280
3469
4052
4075
4108
4283
4702
4850
5231
5307
5394
5635
6050
6104
6316
6330
6370
6422
6431
6465
6646
6719
6926
7059
7212
7354
7361
7460
7730
7765
7808
8267
8428
8459
8614
8623
8642
8683
8725
8739
...

result:

ok 94 numbers

Test #7:

score: 0
Accepted
time: 12ms
memory: 7424kb

input:

13929 89090
3943 8644
13430 3977
3363 5521
59 12914
3684 6027
8689 2811
875 9894
12519 46
9911 7946
9220 12848
11083 12776
954 11196
2335 13503
989 5656
3606 3132
6067 9239
11873 13881
9024 11398
2780 6373
8199 13557
5954 10622
9377 13661
6332 13048
4581 208
5374 262
12840 1399
11491 10000
1136 1096...

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: -100
Wrong Answer
time: 5ms
memory: 6168kb

input:

18592 33482
495 4456
2793 17165
17613 43
15440 3341
13791 11500
5745 2831
8317 5030
16690 13635
9774 15253
4458 18076
292 8865
15473 3700
15565 7800
5480 11172
11778 11072
6370 9249
16035 7071
18529 8649
5226 3750
6662 16399
9579 3216
18386 15177
15243 11103
1202 13431
3535 1061
17783 1529
3340 1828...

output:

1878
20
22
38
40
45
47
60
75
80
94
105
121
125
140
147
149
151
155
165
166
168
185
190
191
205
216
221
222
224
242
251
253
255
263
298
314
325
330
340
347
360
361
362
363
388
389
410
413
420
424
432
441
447
454
468
479
482
493
496
501
533
534
544
557
561
580
589
591
596
629
655
656
672
723
773
784
7...

result:

wrong answer 1st numbers differ - expected: '1879', found: '1878'