QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#478719#996. 割点PYD1#WA 6ms8428kbC++141.9kb2024-07-15 10:33:162024-07-15 10:33:17

Judging History

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

  • [2024-07-15 10:33:17]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:8428kb
  • [2024-07-15 10:33:16]
  • 提交

answer

#include <set>
#include <map>
#include <list>
#include <queue>
#include <cmath>
#include <time.h>
#include <random>
#include <bitset>
#include <vector>
#include <cstdio>
#include <stdio.h>
#include <iomanip>
#include <assert.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define mk make_pair
#define fi first
#define se second

char buf[1 << 20],*p1,*p2;
inline char gc(){
	if (p1 == p2){
		p1 = buf;
		p2 = buf + fread(buf,1,1 << 20,stdin);
	}
	return p1 == p2 ? EOF : *p1++;
	// return getchar();
}

inline int read(){
	int t = 0,f = 1;
	register char c = gc();
	while (c < 48 || c > 57) f = (c == '-') ? (-1) : (f),c = gc();
	while (c >= 48 && c <= 57) t = (t << 1) + (t << 3) + (c ^ 48),c = gc();
	return f * t;
}

const int N = 2e4 + 3,M = 1e5 + 3;
int n,m,etot = 1,dfncnt,head[N],dfn[N],low[N];

struct Edge{
	int u,v,nxt;
}e[M << 1];

inline void adde(int u,int v) {e[++etot] = (Edge){u,v,head[u]},head[u] = etot;}

vector <int> ans;

void Tarjan(int u,int f){
	dfn[u] = low[u] = ++dfncnt;int child = 0;bool flag = 0;
	for (int i = head[u];i;i = e[i].nxt){
		int v = e[i].v;
		if (v == f) continue;
		if (!dfn[v]){
			Tarjan(v,i),low[u] = min(low[u],low[v]),++child;
			if (low[v] >= dfn[u]) flag = 1;
		}else low[u] = min(low[u],dfn[v]);
	}
	if ((f && flag) || (!f && child > 1)) ans.emplace_back(u);
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
#endif
	n = read(),m = read();
	for (int i = 1;i <= m;i++){
		int u = read(),v = read();
		adde(u,v),adde(v,u);
	}
	for (int i = 1;i <= n;i++) if (!dfn[i]) Tarjan(i,0);
	sort(ans.begin(),ans.end());
	printf("%d\n",(int)ans.size());
	for (int p : ans) printf("%d ",p);puts("");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5288kb

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: 6ms
memory: 7812kb

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: 0ms
memory: 7044kb

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: 3ms
memory: 7044kb

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: 4ms
memory: 6612kb

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: 2ms
memory: 6904kb

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: 6ms
memory: 8048kb

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: 0
Accepted
time: 3ms
memory: 6056kb

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:

1879
20 22 38 40 45 47 60 64 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 78...

result:

ok 1880 numbers

Test #9:

score: 0
Accepted
time: 5ms
memory: 7248kb

input:

17167 60477
1940 6602
4942 3281
6066 3302
4044 548
15529 11141
13548 16310
14710 15403
10670 14618
1058 4412
16945 2555
12821 13382
8355 10606
10465 4224
1490 8730
2678 7939
2320 3191
11503 5701
16325 3505
15176 15045
11936 6367
10361 10757
15728 15770
14987 6956
14533 9408
3474 17064
12593 3273
165...

output:

99
368 395 829 949 1434 1687 2506 3126 3316 3695 3893 3899 3940 3963 4118 4250 4284 4452 4551 4580 4978 5167 5174 5199 5318 5370 5433 5509 5843 5941 6372 6414 6462 6810 6903 7014 7045 7048 7303 7400 7695 7780 7853 8309 8369 8411 8739 9288 9397 9415 9550 9601 9969 10188 11064 11115 11127 11172 11268 ...

result:

ok 100 numbers

Test #10:

score: 0
Accepted
time: 0ms
memory: 6448kb

input:

17877 40626
5654 5079
3075 5579
9893 5360
9190 10419
13161 1744
9913 15030
8214 1702
9871 912
6259 11954
12106 73
1577 5597
10513 4871
14614 15252
7712 12156
2536 2511
5758 1637
7716 9225
3746 302
477 1061
492 880
3727 5776
9480 10156
13935 7598
9177 10994
17041 12
1047 3345
12154 6699
5239 3234
299...

output:

870
7 23 26 48 77 81 86 95 113 116 129 132 136 138 157 158 189 195 198 214 215 276 297 310 357 370 371 433 450 473 479 484 488 489 491 502 507 541 552 580 598 694 770 806 820 855 861 867 877 917 946 960 1019 1042 1101 1169 1176 1185 1258 1282 1314 1317 1325 1360 1412 1414 1453 1481 1534 1549 1564 15...

result:

ok 871 numbers

Test #11:

score: 0
Accepted
time: 0ms
memory: 6264kb

input:

11267 45885
6066 9078
8975 36
10789 2389
1377 6287
7827 9168
5567 437
5934 8618
7211 457
4212 10398
827 10386
3697 4725
10185 7551
2196 7928
7437 7039
3245 1309
10462 2498
1841 6446
8950 7901
9054 2566
5770 4781
7030 11038
6119 3067
10738 8762
9504 3971
5076 10433
311 8340
6436 9285
9288 9673
5630 6...

output:

33
179 1214 1819 2037 3116 3277 3329 3338 3727 3910 4407 4540 5096 6070 6325 6333 6495 6992 7218 7317 7465 7763 7803 8235 8443 8702 9272 9506 10019 10261 10409 10784 11234 

result:

ok 34 numbers

Test #12:

score: 0
Accepted
time: 2ms
memory: 7032kb

input:

10331 67610
7252 2455
6307 8496
8030 849
5862 1450
8331 146
7088 2119
1989 9859
2118 8941
3259 2752
4442 8281
2940 3988
5029 6860
2920 6170
9382 4226
2575 8780
5301 2573
2884 7234
225 8596
6800 3536
1634 2571
7115 9400
3128 7049
8597 8722
3057 6244
4668 5316
10218 574
2333 2166
6629 5543
8311 6098
2...

output:

0


result:

ok 1 number(s): "0"

Test #13:

score: 0
Accepted
time: 0ms
memory: 8428kb

input:

13403 97314
8622 7077
3085 9129
10076 3203
12204 8085
12860 1601
6909 10085
7140 9056
12876 11886
2205 13058
10209 7376
10974 3141
1875 11132
9420 12451
239 11669
2811 1724
6739 3794
12989 12003
7658 343
8984 10783
7237 7125
12159 5302
1268 1403
10786 3426
9171 10615
13161 5296
5330 11168
2795 12505...

output:

0


result:

ok 1 number(s): "0"

Test #14:

score: 0
Accepted
time: 4ms
memory: 7992kb

input:

18770 54183
5318 12897
10466 13624
7253 15968
15457 209
17040 12194
11655 10457
14678 1460
8282 7376
1034 17307
15198 3338
5943 2996
1633 13860
13254 9131
4976 1027
12095 9837
9849 17096
4235 7681
10276 8752
12827 17770
14698 12387
12267 11123
11468 13452
16673 11110
1463 10816
17366 13233
18082 813...

output:

336
190 213 247 300 385 397 447 686 690 771 845 877 911 953 991 1106 1186 1196 1205 1227 1246 1329 1520 1779 1787 1839 1858 1877 1899 1900 2140 2155 2180 2186 2207 2221 2251 2283 2380 2386 2556 2564 2579 2620 2621 2632 2680 2754 2759 2790 2810 2828 2837 2862 2962 3004 3023 3027 3090 3238 3278 3287 3...

result:

ok 337 numbers

Test #15:

score: 0
Accepted
time: 3ms
memory: 6520kb

input:

13928 44672
718 3443
8395 819
7538 3592
7368 155
2004 9661
12302 8463
12382 7737
8207 3412
528 3166
2270 10625
12249 9482
5956 3672
5696 3289
12805 4262
8670 3265
1885 127
6976 2963
9649 12854
1784 3840
2202 6517
13504 6326
2448 10311
2606 11627
11302 383
4472 10329
11110 11511
5893 13523
4609 11074...

output:

156
182 194 206 279 296 348 478 480 525 551 729 735 769 774 882 903 967 971 1134 1135 1175 1180 1340 1369 1475 1521 1603 1631 1673 1678 2059 2235 2247 2304 2343 2443 2517 2522 2530 2613 2622 2648 2831 2865 2979 3184 3390 3421 3474 3771 3781 3984 4073 4098 4429 4463 4652 4779 4856 4954 4962 5001 5241...

result:

ok 157 numbers

Test #16:

score: 0
Accepted
time: 5ms
memory: 7344kb

input:

17074 63075
2846 14446
9153 10050
975 7653
2406 1624
4543 663
16820 11056
16890 2526
10970 13057
16366 714
3672 10307
3607 6138
13432 14503
4259 6241
2654 7910
8890 8431
12115 6791
14462 3729
10669 12857
10857 7814
7930 7868
6486 2139
929 293
5921 6917
453 9911
15263 10425
14929 14060
11957 1134
111...

output:

80
961 1344 1422 1523 1896 1958 2014 2016 2076 2302 2423 2680 2726 2743 2810 2936 3131 3238 3301 3705 3729 3948 4008 4148 4199 4288 4366 4545 4722 4848 5270 5545 5576 5783 5867 6414 6576 6811 6907 7309 7316 7513 7914 8369 8601 8923 8931 9147 9190 9232 9610 10023 10411 10554 10901 11117 11318 11656 1...

result:

ok 81 numbers

Test #17:

score: 0
Accepted
time: 5ms
memory: 7736kb

input:

10664 76051
1856 9483
6227 4287
172 4299
5553 2313
10043 1280
1177 3723
8714 4285
3215 4743
7133 8548
726 3464
5804 828
8454 7269
5049 8403
1523 1279
539 6431
1780 532
9812 9111
1861 7175
1193 4368
10330 4039
4581 1409
2145 9684
8638 8117
3050 7099
3966 8397
5382 6930
6477 1400
571 7150
7547 1960
26...

output:

1
9325 

result:

ok 2 number(s): "1 9325"

Test #18:

score: -100
Wrong Answer
time: 3ms
memory: 5888kb

input:

17939 29325
4009 4241
11303 4924
3767 9415
11256 14121
3271 8443
542 17825
2394 9231
6157 7052
17258 6450
7138 3312
6978 5033
12808 2918
13555 10883
1936 11974
1301 9345
3126 17463
16952 4499
4359 730
7833 11498
17263 13454
13801 4282
11803 8376
6714 13220
5855 15469
1472 1130
844 873
6608 1777
5951...

output:

2266
1 4 28 35 38 42 45 48 75 79 90 108 126 133 144 149 156 160 164 169 172 178 183 192 208 219 226 236 252 263 287 288 290 301 310 316 318 324 325 329 330 336 348 378 379 381 386 394 405 428 446 450 454 458 466 471 475 497 504 519 537 539 540 544 545 555 576 581 588 593 595 600 606 607 614 619 623 ...

result:

wrong answer 1st numbers differ - expected: '2268', found: '2266'