QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#479669#898. 二分图最大匹配grass8cow#AC ✓2283ms35600kbC++171.3kb2024-07-15 19:59:442024-07-15 19:59:45

Judging History

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

  • [2024-07-15 19:59:45]
  • 评测
  • 测评结果:AC
  • 用时:2283ms
  • 内存:35600kb
  • [2024-07-15 19:59:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int d[1001000];
int to[1001000],nxt[1001000],cn=1,hd[1010000],S,T;
int flow[1000100];
void ad(int u,int v,int w){
    to[++cn]=v,flow[cn]=w,nxt[cn]=hd[u],hd[u]=cn;
    to[++cn]=u,flow[cn]=0,nxt[cn]=hd[v],hd[v]=cn;
}
const int I=1e9;
int cur[1010000];
bool bfs(){
    for(int i=1;i<=T;i++)d[i]=0,cur[i]=hd[i];
    queue<int>q;q.push(S),d[S]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=hd[u];i;i=nxt[i])if(flow[i]&&!d[to[i]])
            d[to[i]]=d[u]+1,q.push(to[i]);
    }
    return d[T]>0;
}
int dfs(int u,int in){
    if(u==T)return in;int out=0;
    for(int &i=cur[u];i&&in;i=nxt[i])if(flow[i]&&d[to[i]]==d[u]+1){
        int e=dfs(to[i],min(in,flow[i]));
        flow[i]-=e,flow[i^1]+=e;
        in-=e,out+=e;
    }
    if(!out)d[u]=0;
    return out;
}
int n1,n2,m;
int main(){
    scanf("%d%d%d",&n1,&n2,&m);S=n1+n2+1,T=S+1;
    for(int i=1,u,v;i<=m;i++)
        scanf("%d%d",&u,&v),u++,v++,ad(u,v+n1,1);
    for(int i=1;i<=n1;i++)ad(S,i,1);
    for(int i=1;i<=n2;i++)ad(i+n1,T,1);
    int ans=0;
    while(bfs())ans+=dfs(S,I);printf("%d\n",ans);
    for(int i=1;i<=n1;i++)
        for(int j=hd[i];j;j=nxt[j])if(to[j]>n1&&to[j]<S&&!flow[j])
        printf("%d %d\n",i-1,to[j]-1-n1);
    return 0;
}

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

详细

Test #1:

score: 100
Accepted
time: 2262ms
memory: 24476kb

input:

100000 100000 200000
78474 45795
32144 46392
92549 13903
73460 34144
96460 92850
56318 77066
77529 84436
76342 51542
77506 99268
76410 89381
1778 61392
43607 96135
84268 74827
14857 35966
32084 94908
19876 174
1481 94390
12423 55019
64368 92587
81295 7902
25432 46032
36293 61128
73555 84836
8418 102...

output:

100000
0 54731
1 26066
2 89637
3 1717
4 68505
5 28330
6 55261
7 34703
8 42170
9 23249
10 90437
11 69580
12 72086
13 47593
14 29944
15 87183
16 763
17 2814
18 46044
19 75228
20 11487
21 72701
22 60611
23 36775
24 66081
25 45592
26 3321
27 88211
28 71467
29 47516
30 55528
31 83162
32 46298
33 26459
34...

result:

ok OK

Test #2:

score: 0
Accepted
time: 2283ms
memory: 24632kb

input:

100000 100000 200000
56815 52516
2576 76201
40377 1757
50463 66496
15833 50879
9828 16330
80692 9962
51095 17590
15870 35191
91301 65509
90774 57492
11890 8966
44786 41895
3386 35478
93470 47452
84803 93635
90745 34876
18201 38717
7472 34257
36580 19532
13248 27524
6441 69869
8821 61870
94536 67713
...

output:

100000
0 48685
1 54562
2 96282
3 43660
4 56572
5 72097
6 31793
7 12360
8 3023
9 14651
10 80163
11 12379
12 597
13 39076
14 77674
15 94527
16 85130
17 23849
18 35846
19 78842
20 26940
21 93329
22 69417
23 49345
24 65215
25 36147
26 45930
27 84619
28 76814
29 412
30 10858
31 38186
32 60852
33 64942
34...

result:

ok OK

Test #3:

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

input:

4 4 7
1 1
2 2
0 0
3 1
1 2
2 0
3 2

output:

3
1 1
2 0
3 2

result:

ok OK

Test #4:

score: 0
Accepted
time: 69ms
memory: 35600kb

input:

100000 100000 199999
25370 25370
85964 85963
415 415
16796 16796
12437 12437
45409 45408
63005 63004
22155 22155
87828 87827
84013 84013
37307 37307
72324 72324
83703 83703
55390 55389
6780 6779
78090 78090
9375 9375
82192 82192
74694 74694
49841 49841
15798 15798
69855 69854
82948 82947
97389 97388...

output:

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

result:

ok OK

Test #5:

score: 0
Accepted
time: 58ms
memory: 34168kb

input:

100000 100000 199999
59469 59469
76773 76772
89516 89516
87040 87040
90184 90184
83075 83075
61454 61454
33615 33615
85794 85793
92072 92071
49725 49725
63842 63841
99247 99247
24121 24121
29552 29551
73533 73533
75845 75845
27029 27028
84418 84418
26636 26636
10100 10099
75013 75012
67341 67341
756...

output:

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

result:

ok OK

Test #6:

score: 0
Accepted
time: 2280ms
memory: 24672kb

input:

100000 100000 199999
22284 45795
32144 44930
58734 13903
57136 34144
7548 92850
56318 11874
77529 85278
27039 51542
77506 94257
69265 89381
67073 61392
86159 96135
83227 74827
14857 19500
32084 73639
86884 174
27268 94390
20020 55019
45357 92587
17833 7902
55801 46032
36293 46557
73555 13746
8418 88...

output:

100000
0 2401
1 18084
2 59700
3 99457
4 33291
5 38417
6 97167
7 64564
8 28471
9 68817
10 62095
11 31609
12 57675
13 28348
14 2599
15 99163
16 58923
17 17629
18 3975
19 53920
20 25930
21 4206
22 49364
23 55768
24 40573
25 87244
26 12858
27 39608
28 42953
29 68974
30 89214
31 48329
32 3980
33 50041
34...

result:

ok OK

Test #7:

score: 0
Accepted
time: 2245ms
memory: 27708kb

input:

100000 100000 199999
4850 52516
2576 29250
69016 1757
85854 66496
48300 50879
83741 16330
98931 9962
38730 17590
15870 13960
91301 97595
81692 57492
11890 59332
5076 41895
23574 35478
93470 65245
61976 93635
96140 34876
18201 35366
64057 34257
25588 19532
13248 91003
6441 83448
99191 61870
94536 169...

output:

100000
0 39785
1 26716
2 6189
3 33390
4 12388
5 6804
6 66264
7 36155
8 25212
9 73214
10 29914
11 87445
12 9428
13 44486
14 83326
15 61240
16 63409
17 15512
18 77732
19 17216
20 39374
21 7319
22 36983
23 45568
24 34087
25 31512
26 83824
27 73657
28 80853
29 58211
30 14867
31 17935
32 49451
33 91463
3...

result:

ok OK

Test #8:

score: 0
Accepted
time: 103ms
memory: 20840kb

input:

61217 61379 199943
14003 13749
24504 24347
30371 30219
27661 27461
33247 33397
38346 38157
17300 16944
50476 50643
56488 56551
46690 46949
21355 21288
3899 3659
24330 24165
8806 8305
40957 40994
15089 14813
20397 20389
30864 30800
33635 33755
20900 20808
55447 55499
4335 4040
36726 36551
16496 16095...

output:

37154
10 0
11 3
12 6
13 9
14 10
15 1
16 4
17 7
18 11
19 2
20 13
21 8
28 14
29 15
30 32
31 26
32 24
33 29
34 28
35 20
36 46
39 47
41 44
44 40
45 39
46 38
57 51
58 53
59 54
60 52
61 55
64 60
66 57
70 61
71 63
79 73
80 70
83 71
84 74
85 68
86 69
87 75
89 78
90 76
91 77
96 80
104 79
107 85
113 96
126 95...

result:

ok OK

Test #9:

score: 0
Accepted
time: 101ms
memory: 22884kb

input:

61352 60513 199960
2270 2419
38842 39327
48788 48843
2493 2635
40183 40659
59754 59010
48980 48993
52508 52276
12892 13195
33811 34565
40260 40700
2116 2289
11742 12133
29439 29942
4256 4392
51422 51263
44695 44994
21600 22165
21666 22208
26472 26785
49979 50038
12099 12515
10539 10816
32736 33401
3...

output:

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

result:

ok OK

Test #10:

score: 0
Accepted
time: 230ms
memory: 23532kb

input:

100000 100000 199998
0 13805
0 33641
1 9259
1 62738
1 70691
1 78118
2 41148
3 15765
3 50059
4 96644
5 91521
6 32562
8 2550
8 11396
8 48345
9 14639
9 51057
9 79293
9 92374
10 64733
10 67020
11 7764
11 46822
11 60302
12 8749
12 27869
12 69569
12 71510
13 35684
13 42579
13 82023
14 34778
15 1975
15 693...

output:

78404
0 13805
1 78118
2 41148
3 15765
5 91521
6 32562
8 48345
9 79293
10 67020
12 71510
13 42579
14 34778
15 69322
16 57308
17 6162
18 52651
19 64579
21 24593
22 97997
23 77417
24 47998
25 24157
28 67932
29 65316
30 31954
31 19608
32 71996
34 98186
35 72885
36 89653
37 57779
39 36111
40 1530
41 6095...

result:

ok OK

Test #11:

score: 0
Accepted
time: 249ms
memory: 23028kb

input:

100000 100000 199998
0 28389
0 41333
0 66666
1 5984
1 15912
3 63753
3 77735
4 25015
4 30450
4 90212
5 66978
5 98909
6 63465
6 78227
6 78950
6 85422
7 1743
7 1868
7 55171
8 37582
9 26491
9 82984
10 29229
10 29811
10 33063
11 10609
11 48601
11 73298
11 95658
12 29064
12 50261
12 63186
12 68616
13 8683...

output:

78497
0 41333
3 63753
4 30450
5 98909
7 1868
10 33063
11 10609
12 68616
13 86837
15 77990
16 16525
18 93717
19 32559
21 15495
23 56994
25 47612
26 36458
27 33773
30 28313
31 82347
33 96004
34 35265
35 82877
36 24476
37 52477
39 94787
41 52015
42 99374
43 36190
45 52943
46 23141
48 34244
51 94147
52 ...

result:

ok OK

Test #12:

score: 0
Accepted
time: 237ms
memory: 21260kb

input:

100000 100000 199997
0 4357
0 35525
0 51857
1 57468
1 94927
1 96004
3 75468
4 20202
4 37102
5 32207
6 8677
6 16775
6 46813
6 75640
7 30806
8 4099
8 26454
8 49376
8 55539
8 67032
9 82362
10 11387
10 33778
10 35352
10 50533
10 54706
11 44868
11 59104
14 80528
14 90600
14 99752
15 10954
15 80519
15 873...

output:

78379
1 57468
3 75468
6 46813
7 30806
8 26454
10 54706
11 59104
14 80528
16 32645
19 49350
20 58977
21 31926
22 50244
23 5726
24 92464
26 52648
27 57836
28 96888
30 50525
31 76950
32 73647
33 971
35 81872
36 660
37 65791
38 55672
39 29124
41 27121
44 77986
46 2959
48 91397
51 66821
52 87844
54 77781...

result:

ok OK

Test #13:

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

input:

17707 77101 11866
4 29611
4 62770
4 65605
5 22177
5 57724
14 59632
14 68649
17 9622
18 9221
18 43355
29 19612
30 44428
32 51277
34 53196
35 20939
37 68142
38 34663
38 36432
39 71932
40 62217
41 40291
43 53542
44 22018
44 60539
47 56819
47 76081
49 18326
50 52876
50 58006
51 64709
51 66011
52 26751
5...

output:

8453
4 65605
5 57724
14 68649
17 9622
18 43355
29 19612
30 44428
32 51277
34 53196
35 20939
37 68142
38 36432
39 71932
40 62217
43 53542
44 60539
47 76081
50 58006
51 66011
52 45116
54 5453
55 72966
57 8366
58 70074
59 16851
60 59385
62 16210
67 18050
68 27089
70 47489
71 41622
73 59911
74 70531
76 ...

result:

ok OK

Test #14:

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

input:

69830 19691 148749
0 8565
0 12093
0 12608
2 777
2 8771
3 6106
3 7526
3 10596
3 12199
3 14674
3 17676
4 4643
4 15016
4 17194
6 6948
7 1743
7 7750
8 2305
8 4814
9 4468
9 12246
9 16763
9 17448
10 295
10 12043
10 13971
11 168
11 4447
11 7762
11 15833
11 15993
12 1914
12 3080
12 5649
14 29
15 1675
15 464...

output:

19684
668 6774
847 606
1602 11215
1618 5082
2193 14844
2356 13543
2615 17856
3482 1570
3603 7499
3758 6608
3880 2324
4703 14155
4731 16394
5166 2647
5174 2124
5205 4310
5214 439
5217 11249
5510 1121
5648 7433
5678 720
5680 5562
5808 1941
5903 1332
5985 4567
6002 2875
6535 10687
6924 8314
6977 8736
7...

result:

ok OK

Test #15:

score: 0
Accepted
time: 66ms
memory: 19084kb

input:

53336 61958 92222
0 23730
0 34075
0 35525
1 30468
1 61015
3 24509
3 36308
4 8061
4 45185
4 54435
5 32530
5 59288
6 10104
6 56657
10 2203
10 3106
10 33778
11 29821
11 59104
12 27897
14 18850
15 13472
15 14983
15 37131
15 40140
15 49346
15 59901
16 12876
16 32645
18 26571
21 60370
22 39980
22 41044
22...

output:

40194
0 34075
1 61015
3 24509
4 45185
5 59288
11 29821
12 27897
15 37131
16 12876
21 60370
22 41044
23 59945
24 17646
25 7805
26 55641
27 528
28 37215
29 61757
30 51900
32 18385
33 14342
34 19082
35 30280
36 24688
39 53021
42 10909
43 28881
45 10878
47 25324
49 28754
50 41229
52 41546
53 39764
54 24...

result:

ok OK

Test #16:

score: 0
Accepted
time: 63ms
memory: 18600kb

input:

36033 25839 130375
0 1577
0 16725
0 22301
0 24558
1 5977
1 6738
1 9339
1 25294
2 762
2 6992
2 10207
2 14608
3 3
3 3002
3 25047
4 12402
4 13815
4 15862
5 4727
6 6680
6 8345
6 10057
6 13352
6 17084
7 9878
7 17893
7 21628
7 23892
8 2601
8 13004
8 19099
8 23028
9 2307
9 13011
9 15776
9 22642
11 7388
11 ...

output:

25668
0 1577
4 15862
7 9878
25 10609
29 9367
31 1566
33 11274
37 165
52 4696
54 18108
55 11897
80 6783
92 17184
96 3321
106 1856
107 16666
108 23586
115 12674
116 13458
121 14106
123 4546
124 4942
127 794
131 9058
133 4574
138 3450
142 8704
150 7379
155 14162
159 6829
163 6665
166 10404
169 2412
180...

result:

ok OK

Test #17:

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

input:

14868 99117 25214
0 19546
0 37951
1 13804
1 18263
1 38541
1 49319
1 64693
1 81665
1 91777
2 2159
2 8896
4 38134
5 3464
5 52631
6 85971
6 92674
7 5530
7 12991
7 35465
8 12077
8 71946
9 57520
11 75486
11 95227
12 83001
13 83429
13 85532
15 32388
15 49234
15 87159
16 70733
16 95797
17 45027
18 51284
20...

output:

12003
0 37951
1 91777
2 8896
4 38134
5 52631
6 92674
7 35465
8 12077
9 57520
11 95227
12 83001
13 85532
15 87159
16 95797
17 45027
18 51284
20 59547
21 5520
23 86112
26 29339
27 18534
28 31861
30 49493
33 30727
34 40008
37 81810
38 72113
39 11712
40 81311
41 75321
43 49309
44 83232
46 77294
47 92399...

result:

ok OK

Test #18:

score: 0
Accepted
time: 18ms
memory: 22572kb

input:

53098 9437 57924
0 262
0 3336
0 7251
2 2976
3 4877
4 3403
4 8279
5 4742
6 2961
6 8901
8 5979
8 8808
9 7822
10 415
12 969
13 1058
15 3592
17 5759
18 7128
19 4461
19 9343
20 5011
20 8942
21 8414
22 5217
22 5266
22 5455
23 5698
23 8697
24 5855
25 1211
25 2830
28 3685
29 1866
29 8645
32 6955
32 7045
33 ...

output:

9415
78 2123
98 1545
192 8384
415 908
848 1206
945 2497
1133 51
1644 4440
1883 1987
2635 1286
2673 981
3029 157
3043 211
3313 3513
3548 7190
3782 5055
3892 4661
3984 375
4002 341
4007 6676
4105 7457
4172 533
4189 252
4390 4566
4497 7011
4666 1763
4681 8771
4707 4379
4746 5111
4798 2134
4854 5527
501...

result:

ok OK

Test #19:

score: 0
Accepted
time: 269ms
memory: 20888kb

input:

62342 62612 153201
0 1819
1 26257
1 34654
1 41966
2 9609
3 19007
3 31306
3 36054
4 36681
4 42043
4 46885
4 54123
5 35272
5 48535
6 9177
6 44477
7 11189
7 17566
7 41426
7 53724
8 13815
8 36015
8 48166
10 1144
10 2928
10 21148
10 21677
10 46645
12 39907
12 53275
13 52579
14 21089
15 39807
16 46513
17 ...

output:

53671
1 41966
3 31306
4 36681
6 9177
7 41426
8 48166
10 1144
15 39807
16 46513
17 57314
18 53192
20 58031
22 30788
24 43728
27 53143
28 60322
29 45277
30 49076
31 16727
32 22621
33 6527
34 57171
36 9660
37 13583
38 10615
39 28697
43 43072
44 15631
45 39372
46 34156
47 3233
48 18899
50 24067
51 16032...

result:

ok OK

Test #20:

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

input:

95835 11475 31126
7 7489
10 1813
17 1852
18 9253
21 2999
25 1649
28 7088
33 4068
33 6119
34 5651
39 10350
41 5703
43 7512
51 3934
52 4246
55 4275
55 6549
64 8185
66 10080
67 10332
73 6343
73 6432
80 8844
86 1764
87 5646
92 399
95 509
95 9564
102 10598
107 582
121 5613
122 5866
123 7063
125 4180
125 ...

output:

10716
123 7063
137 7604
144 3682
188 4648
197 4971
262 8971
264 111
334 10609
364 7311
386 8103
394 3910
524 6307
540 10058
564 3602
581 4078
629 5299
653 6060
660 4249
669 4906
679 4647
752 5229
762 2742
869 2933
922 2489
927 1545
951 7734
968 580
1004 8125
1047 5593
1066 6281
1222 7310
1264 3838
1...

result:

ok OK

Test #21:

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

input:

5824 49455 192460
0 451
0 2959
0 4380
0 4902
0 9092
0 9318
0 10189
0 11109
0 13730
0 15872
0 17604
0 18557
0 19327
0 19871
0 21171
0 24112
0 26985
0 28368
0 28474
0 29569
0 30903
0 31861
0 35960
0 36791
0 38654
0 40350
0 46164
0 46921
0 47526
0 48226
0 48323
0 48592
0 49186
1 2866
1 8429
1 9731
1 98...

output:

5824
0 46164
1 42273
2 43936
3 44252
4 38734
5 43336
6 45637
7 43357
8 45814
9 41048
10 47432
11 44981
12 44043
13 44199
14 42833
15 42083
16 43133
17 44171
18 43692
19 43727
20 39500
21 41663
22 43741
23 42841
24 43640
25 46018
26 43841
27 44651
28 48500
29 42882
30 46279
31 43862
32 44382
33 45960...

result:

ok OK

Test #22:

score: 0
Accepted
time: 41ms
memory: 20976kb

input:

64506 23320 150593
0 4768
0 10542
0 14842
0 20602
1 1266
1 12253
2 471
2 13145
2 14023
2 15190
2 18272
2 22689
4 8149
4 9069
6 357
6 10397
6 10869
6 16797
7 5497
7 19179
8 3468
8 6448
8 11473
8 12455
8 13155
9 751
10 11245
11 10586
11 13266
11 17148
11 20206
11 22535
12 5515
13 374
13 19047
14 11867...

output:

23290
70 16298
280 2648
358 19371
476 4120
557 15534
627 16034
660 20221
798 16539
815 2041
821 5172
856 4403
927 18662
945 5500
1122 648
1182 18410
1191 15540
1192 2738
1252 4864
1269 8726
1275 122
1319 4352
1354 18142
1445 338
1605 15744
1639 375
1705 7772
1734 19530
1984 4314
2063 12763
2150 5016...

result:

ok OK