QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#465519#999. 边双连通分量wsc2008#AC ✓92ms62332kbC++141.8kb2024-07-06 23:58:132024-07-06 23:58:13

Judging History

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

  • [2024-07-06 23:58:13]
  • 评测
  • 测评结果:AC
  • 用时:92ms
  • 内存:62332kb
  • [2024-07-06 23:58:13]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=1e6+9;
ll n,m,hd[N],tot=1,U[N],V[N];
ll dfn[N],low[N],cut[N],tim;
struct Edg{
    ll to,nxt;
}es[N];
void adde(ll x,ll y){
    es[++tot]=(Edg){y,hd[x]};
    hd[x]=tot;
}
void tarjan(ll x,ll lst){
    dfn[x]=low[x]=++tim;
    for(ll i=hd[x];i;i=es[i].nxt){
        if((i^lst)==1)continue;
        ll y=es[i].to;
        if(!dfn[y]){
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x])cut[i>>1]=1;
        }
        else low[x]=min(low[x],dfn[y]);
    }
}
vector<ll>res[N];
ll cnt,bel[N];
void dfs(ll x){
    bel[x]=cnt;
    res[cnt].push_back(x);
    for(ll i=hd[x];i;i=es[i].nxt){
        ll y=es[i].to;
        if(cut[i>>1])continue;
        if(bel[y])continue;
        dfs(y);
    }
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    n=read(),m=read();
    rep(i,1,m){
        ll x=read(),y=read();
        x++,y++;
        U[i]=x,V[i]=y;
        adde(x,y),adde(y,x);
    }
    rep(i,1,n){
        if(!dfn[i])tarjan(i,0);
    }
    rep(i,1,n){
        if(!bel[i])cnt++,dfs(i);
    }
    write(cnt),putchar('\n');
    rep(i,1,cnt){
        write(res[i].size()),putchar(' ');
        for(ll x:res[i])write(x-1),putchar(' ');
        putchar('\n');
    }
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 34500kb

input:

4 5
0 2
0 1
3 0
2 1
2 3

output:

1
4 0 3 2 1 

result:

ok OK

Test #2:

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

input:

13 21
4 5
8 7
12 3
3 10
1 5
10 2
0 0
11 4
2 12
9 1
9 0
7 8
7 6
9 1
8 2
12 10
11 0
8 6
3 2
5 9
4 11

output:

3
6 0 11 4 5 9 1 
4 2 3 10 12 
3 6 8 7 

result:

ok OK

Test #3:

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

input:

2 2
0 1
1 0

output:

1
2 0 1 

result:

ok OK

Test #4:

score: 0
Accepted
time: 92ms
memory: 62332kb

input:

200000 200000
127668 148778
77100 11865
85144 199231
39485 84917
102044 187263
130204 174776
26220 198288
162188 12078
92196 146334
120537 38083
150353 160479
18707 6545
101149 25450
62271 9177
38892 6454
11709 191939
89247 145109
140599 121858
197410 148980
55975 169098
128576 59852
68224 182347
89...

output:

105340
1 0 
94661 1 81390 152391 22352 89186 45552 120699 190664 62030 77594 184747 153510 130907 109651 111583 103836 83676 76270 74513 24169 190 34772 62656 165492 44029 100847 198281 172345 50988 157417 81369 143303 29039 175495 145757 150280 96757 63227 90612 82632 56020 132501 97095 71772 52063...

result:

ok OK

Test #5:

score: 0
Accepted
time: 79ms
memory: 62012kb

input:

200000 200000
150762 148756
172967 108322
69862 125085
84513 111056
141009 156725
36311 103205
31879 79919
62895 63377
21697 115522
161610 160423
113104 10277
106927 168428
136657 198931
52292 164110
149020 7038
115111 112823
35584 124385
45429 191603
96444 30523
195578 149089
160105 58103
139792 27...

output:

104955
95046 0 52721 190891 164233 136949 3012 153103 38758 37445 43103 137815 60121 74400 150650 6405 52869 39525 43994 79195 144942 80162 7806 105725 189293 36887 65604 69454 44788 43317 161381 179884 64239 114320 157747 187161 156795 173640 153523 40292 107734 14721 119087 171338 105102 4598 2535...

result:

ok OK

Test #6:

score: 0
Accepted
time: 83ms
memory: 61092kb

input:

200000 200000
53335 120202
193029 92221
8244 61648
50176 7825
97274 91479
85438 76999
26861 80116
162826 198446
160509 95916
143190 116619
121254 192931
121545 132273
149400 91882
97032 5048
179008 82221
187475 70697
159074 65868
158744 94466
120006 170635
36429 162768
61114 17876
131798 188508
1080...

output:

105649
94350 0 133179 189046 103625 132225 173468 40175 65049 12608 15331 39384 57106 138749 117594 143994 46712 36920 9490 19692 38801 22086 166241 70241 122125 147422 187045 195765 169167 94499 128189 52661 93757 10592 67354 4606 53731 62621 56872 73283 65932 181820 184939 140936 162172 27489 1088...

result:

ok OK

Test #7:

score: 0
Accepted
time: 55ms
memory: 53300kb

input:

127669 148779
124640 77100
11865 117450
85144 68159
104241 39485
76372 84917
102044 56191
43704 26220
67216 31116
75749 123504
12078 92196
70006 15262
100591 74552
120537 38083
19281 29407
18707 6545
101149 25450
62271 9177
38892 6454
11709 119710
60867 89247
14037 9527
121858 66338
112298 81804
795...

output:

51131
76537 0 110791 73038 34815 58319 102824 45525 59421 108995 65318 111411 36280 89008 35818 12542 42649 727 70138 15213 44392 37142 115705 84532 39441 117947 43496 21456 61872 56403 51212 45177 23627 125455 115904 116381 124702 71453 99722 63914 19723 52842 59529 100187 83962 47122 117402 28214 ...

result:

ok OK

Test #8:

score: 0
Accepted
time: 60ms
memory: 54684kb

input:

150763 148757
108322 69862
125085 84513
111056 141009
36311 103205
31879 79919
62895 63377
21697 115522
113104 10277
106927 136657
52292 149020
7038 115111
112823 35584
124385 45429
96444 30523
149089 58103
139792 27250
15883 109949
69372 132387
141930 113408
65522 128254
138198 141969
42522 92075
1...

output:

81019
69744 0 52721 61467 97726 42461 31420 40158 101554 46452 61719 42971 135893 24809 109158 111070 28061 35298 115630 6917 19449 55041 90515 76393 126762 141171 112245 97324 44551 14188 104013 15578 38336 94608 70255 121170 88038 141421 63791 9643 149312 116429 67699 121949 132925 109789 132259 1...

result:

ok OK

Test #9:

score: 0
Accepted
time: 31ms
memory: 47188kb

input:

53336 120203
26685 8244
50176 7825
31738 24370
25943 19902
11463 26861
29977 26309
14580 31754
1838 29437
30380 12118
51083 31633
1201 18328
26346 5295
48935 19027
31496 19906
41783 5048
47936 16685
5161 34107
15907 28002
332 27672
28930 39563
36429 31696
17876 726
42526 21682
35319 8727
17974 25252...

output:

3392
49945 0 39419 45573 44086 27683 6798 47654 7911 11797 14814 11922 1083 47995 15924 43946 30439 3159 47035 9478 31661 563 52479 22224 37105 15709 44346 33664 47832 13783 51741 45477 49618 28721 11377 16454 41336 5065 31167 22304 49187 39267 20303 17985 30984 47710 46283 22769 44664 23591 16834 2...

result:

ok OK

Test #10:

score: 0
Accepted
time: 16ms
memory: 39700kb

input:

17707 71661
1354 3272
13699 17294
16733 9246
14993 5758
7252 2983
3813 6121
10450 14069
8088 11201
857 4420
12788 2032
11938 1465
10322 15171
14688 1857
2309 2742
2013 13200
14142 16319
10541 1922
10368 1516
7994 9092
3327 5166
13484 2876
15472 13522
15622 13479
3361 15314
15464 14974
17637 7535
435...

output:

75
16444 0 13373 10861 4635 11171 14234 12358 16807 6688 11695 2537 11523 6402 1851 925 9635 7519 2882 9895 7173 4192 9179 6263 12412 14220 17609 14227 6951 10078 8900 8939 3733 8887 16184 7340 9872 11730 7241 3943 7865 12881 17589 5144 7851 6048 13072 2867 10634 786 10036 12266 2842 11957 13552 440...

result:

ok OK

Test #11:

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

input:

4294 17517
1175 3250
314 389
4272 3633
2938 1831
1307 2818
3321 347
1205 1428
2354 1478
1003 3898
1587 3443
1122 1512
2512 3995
348 3280
2064 1022
1834 2958
4281 1863
689 3613
2115 3708
1645 1488
1601 4181
916 4276
128 2626
4147 2868
87 1411
1802 1451
1254 2010
2936 3120
1065 277
1121 3284
3655 2849...

output:

29
3031 0 1326 1032 1925 3799 3819 2549 4098 2738 3702 3760 2850 513 3189 798 330 2145 2623 2554 2955 2829 937 4069 18 413 900 3030 594 2208 2390 789 2591 3051 2228 2149 4239 1137 2427 64 1287 1355 2710 3420 2364 2868 2030 3922 1830 1720 3138 2148 27 2802 1077 1395 142 4063 3316 1622 2307 4147 2295 ...

result:

ok OK

Test #12:

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

input:

26686 105813
14774 5315
22701 21346
1398 13888
18566 18745
22298 6181
21347 10653
16500 23768
2329 5818
17512 16769
25519 338
12580 3064
19467 21665
3978 13202
23556 25178
195 9695
1472 13111
22925 24074
3026 13281
17666 14469
22007 18680
4159 13152
20431 23814
6671 10788
24433 13211
9794 12608
3264...

output:

137
11036 0 10881 7203 18541 5805 25311 21546 26664 21759 6341 11935 1720 19359 16326 24573 5312 2788 25557 25479 13044 14565 16522 4866 9970 17586 10402 19910 13142 15342 18045 7663 13539 15514 13741 18142 14538 9169 713 14675 21094 8982 3960 21050 12896 12707 23068 13022 4164 10810 25923 18068 663...

result:

ok OK

Test #13:

score: 0
Accepted
time: 23ms
memory: 44376kb

input:

36033 148595
33366 22486
14414 23855
2694 30361
16352 31902
27993 2048
4707 31743
30610 12884
23278 27069
10529 20914
2030 30015
24554 15673
10184 29423
17825 20383
34077 1181
25518 26129
6355 8810
2857 21736
25108 34280
14992 24299
32649 20227
34529 10407
23194 29913
10451 319
34666 8904
30811 3003...

output:

150
7961 0 8630 4929 27050 9220 14736 4117 4908 10947 6498 27469 13587 36031 29899 29576 11510 2957 12223 22436 8383 19919 3453 24244 32110 27377 32231 31035 1345 17226 4653 5198 18063 28991 4471 20808 3752 35869 9601 19051 606 26247 21846 502 32977 35713 23917 24526 7533 26226 12962 1218 3514 16339...

result:

ok OK

Test #14:

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

input:

14868 57739
5724 2103
9214 3074
2269 531
3811 13162
5199 12632
6337 12078
12592 4977
3553 6975
5063 6622
1221 13056
4252 3705
7547 7879
1702 3685
4058 2503
7540 9423
4280 12228
574 6265
11876 2711
4805 7605
1468 4802
6921 1954
6350 2733
4429 5862
13549 14543
13809 5357
1509 11478
87 2676
6299 7060
1...

output:

80
5372 0 4810 11106 14440 5315 6482 3882 14234 1406 2596 12457 5415 14614 13419 12879 5091 5766 6154 6179 6825 13088 14653 9582 10999 6951 5579 1896 6085 11330 6148 7333 2993 11235 8013 13171 4061 6046 7341 4278 5532 2676 10234 8135 2914 6614 5761 2380 14004 1091 6258 10301 11484 3341 1472 3522 117...

result:

ok OK

Test #15:

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

input:

53 43
32 44
25 10
24 49
20 28
28 44
16 12
37 48
46 36
30 47
25 3
17 31
19 17
29 42
25 44
30 3
31 21
2 34
42 12
22 50
12 52
39 10
0 46
29 1
12 21
3 0
11 31
42 25
4 51
26 36
19 48
39 26
5 21
7 41
29 34
38 47
29 8
26 17
42 46
36 20
39 30
13 27
28 31
27 24

output:

37
17 0 3 30 39 26 17 31 28 44 25 42 46 36 20 12 21 10 
1 1 
1 2 
1 4 
1 5 
1 6 
1 7 
1 8 
1 9 
1 11 
1 13 
1 14 
1 15 
1 16 
1 18 
1 19 
1 22 
1 23 
1 24 
1 27 
1 29 
1 32 
1 33 
1 34 
1 35 
1 37 
1 38 
1 40 
1 41 
1 43 
1 45 
1 47 
1 48 
1 49 
1 50 
1 51 
1 52 

result:

ok OK

Test #16:

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

input:

70 21
39 34
29 33
38 53
37 7
47 64
47 17
65 66
60 39
37 47
19 68
14 28
39 41
52 55
0 60
59 16
11 40
11 33
35 26
0 11
24 17
26 43

output:

70
1 0 
1 1 
1 2 
1 3 
1 4 
1 5 
1 6 
1 7 
1 8 
1 9 
1 10 
1 11 
1 12 
1 13 
1 14 
1 15 
1 16 
1 17 
1 18 
1 19 
1 20 
1 21 
1 22 
1 23 
1 24 
1 25 
1 26 
1 27 
1 28 
1 29 
1 30 
1 31 
1 32 
1 33 
1 34 
1 35 
1 36 
1 37 
1 38 
1 39 
1 40 
1 41 
1 42 
1 43 
1 44 
1 45 
1 46 
1 47 
1 48 
1 49 
1 50 
1...

result:

ok OK

Test #17:

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

input:

88 139
5 61
52 80
0 17
50 87
62 71
25 69
10 46
44 86
11 38
17 35
73 49
24 47
39 83
8 66
55 56
64 45
83 41
59 35
76 24
2 70
11 77
80 58
84 86
30 50
23 54
36 74
12 10
62 75
33 34
43 28
77 29
10 46
77 33
26 48
32 38
52 79
15 30
25 57
86 0
46 75
81 60
35 83
66 87
25 86
19 85
9 38
15 64
59 82
0 53
40 66
...

output:

16
73 0 72 20 61 57 28 37 5 1 55 56 17 70 49 6 9 7 2 21 33 73 77 14 22 41 23 60 81 25 86 66 15 48 79 39 83 35 27 36 11 38 85 30 50 87 52 78 3 62 71 75 4 8 46 10 59 24 76 32 65 80 26 58 44 64 29 19 63 69 40 84 67 43 
1 12 
1 13 
1 16 
1 18 
1 31 
1 34 
1 42 
1 45 
1 47 
1 51 
1 53 
1 54 
1 68 
1 74 
...

result:

ok OK

Test #18:

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

input:

53 185
48 40
23 7
45 7
6 42
13 6
45 1
18 28
47 14
11 15
27 9
50 44
23 47
20 27
18 19
2 19
18 49
32 49
9 12
11 0
32 49
22 14
8 48
41 28
30 43
4 21
7 22
28 30
17 11
19 30
44 7
46 8
50 45
35 48
29 47
4 26
16 39
37 25
38 12
19 52
28 41
23 31
33 34
6 15
44 24
0 6
26 22
49 43
4 31
20 38
43 39
41 39
51 40
...

output:

3
20 0 8 17 13 42 9 40 11 15 6 38 27 48 35 46 10 51 3 20 12 
16 1 24 21 44 47 22 4 45 31 14 29 50 5 26 7 23 
17 2 43 18 25 49 52 39 36 19 28 34 37 41 16 30 33 32 

result:

ok OK

Test #19:

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

input:

70 252
63 36
64 48
26 34
43 37
30 53
67 64
26 19
25 54
28 44
52 60
4 22
43 48
14 48
12 50
37 23
28 40
48 54
60 23
43 46
7 5
29 39
5 13
57 60
1 23
33 8
59 39
3 29
5 8
34 11
44 40
39 19
40 17
42 48
39 19
49 46
0 48
46 45
57 67
43 60
56 59
32 42
6 54
56 69
23 43
38 65
66 24
0 64
16 10
23 1
4 16
37 49
5...

output:

1
70 0 52 25 32 51 54 14 43 45 49 48 67 22 65 31 44 17 38 55 61 8 53 41 56 62 2 12 33 5 39 50 29 59 11 7 35 30 18 21 26 68 9 13 69 19 34 3 6 60 64 15 42 23 57 1 37 46 66 47 24 10 36 63 16 4 28 40 27 58 20 

result:

ok OK

Test #20:

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

input:

88 390
74 40
14 37
44 66
7 49
12 4
39 48
56 76
46 40
80 30
5 39
52 0
40 79
0 11
34 41
43 80
54 62
61 41
54 37
31 81
59 66
23 59
47 84
16 85
68 29
31 63
4 55
27 5
26 68
14 84
16 34
82 16
62 54
46 15
65 63
58 83
5 36
67 19
65 42
35 25
82 73
55 59
28 36
22 38
46 79
61 34
51 40
69 42
36 5
26 38
86 14
22...

output:

3
76 0 52 45 75 11 49 50 6 64 24 86 28 7 14 84 78 47 54 37 62 10 69 65 63 8 31 13 81 67 19 25 87 35 32 21 58 83 70 18 3 15 46 74 79 17 40 51 29 38 22 68 26 12 53 55 23 4 44 59 66 73 1 43 80 30 72 2 82 61 41 57 34 16 85 71 42 
6 5 27 36 48 39 60 
6 9 76 56 33 77 20 

result:

ok OK