QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#480881#898. 二分图最大匹配ItheaValgulious#AC ✓2569ms34716kbC++142.1kb2024-07-16 19:23:592024-07-16 19:24:00

Judging History

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

  • [2024-07-16 19:24:00]
  • 评测
  • 测评结果:AC
  • 用时:2569ms
  • 内存:34716kb
  • [2024-07-16 19:23:59]
  • 提交

answer

#include<iostream>
#include<climits>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<array>
#define endl '\n'
using namespace std;
using ll = long long;
using pi2 = array<int,2>;
using pi3 = array<int,3>;

const int N=2e5+500,M=4e5+50;
struct Edge{
    int u,v,w,nxt;
} edges[M*2];
int head[N],ecnt;
void add_edge_(int u,int v,int w){
    edges[++ecnt]={u,v,w,head[u]};
    head[u]=ecnt;
}
void add_edge(int u,int v,int w){
    add_edge_(u,v,w),add_edge_(v,u,0);
}
int cpy[N],dis[N];
bool bfs(int s,int t){
    memcpy(cpy,head,sizeof(cpy)),memset(dis,0x3f,sizeof(dis));
    queue<int> q;
    q.push(s),dis[s]=0;
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=edges[i].nxt){
            if(edges[i].w&&dis[edges[i].v]>dis[edges[i].u]+1){
                dis[edges[i].v]=dis[edges[i].u]+1;
                q.push(edges[i].v);
            }
        }
    }
    return dis[t]<0x3f3f3f3f;
}
ll dfs(int u,int t,int minf){
    if(u==t||!minf)return minf;
    ll f,flow=0;
    for(int &i=cpy[u];i;i=edges[i].nxt){
        if(edges[i].w&&dis[edges[i].v]==dis[edges[i].u]+1){
            if(f=dfs(edges[i].v,t,min(edges[i].w,minf))){
                flow+=f,minf-=f,edges[i].w-=f,edges[((i-1)^1)+1].w+=f;
                if(!minf)return flow;
            }else{
                dis[edges[i].v]=-1;
            }
        }
    }
    return flow;
}
ll dinic(int s,int t){
    ll flow=0;
    while(bfs(s,t))
        flow+=dfs(s,t,INT_MAX);
    return flow;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n1,n2,m,s,t;
    cin>>n1>>n2>>m;
    s=n1+n2+1,t=s+1;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        u++,v++;
        add_edge(u,v+n1,1);
    }
    for(int i=1;i<=n1;i++)add_edge(s,i,1);
    for(int i=1;i<=n2;i++)add_edge(i+n1,t,1);
    int f=dinic(s,t);
    cout<<f<<endl;
    for(int i=1;i<=ecnt;i++){
        if(edges[i].u<=n1&&edges[i].v<=n1+n2&&edges[i].w==0){
            cout<<edges[i].u-1<<" "<<edges[i].v-n1-1<<endl;
        }
    }
    return 0;
}

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

詳細信息

Test #1:

score: 100
Accepted
time: 2569ms
memory: 23128kb

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
78474 45795
92549 13903
73460 34144
96460 92850
76342 51542
76410 89381
1778 61392
43607 96135
84268 74827
19876 174
1481 94390
12423 55019
64368 92587
81295 7902
25432 46032
7004 23282
29100 60189
70797 28664
49166 48275
56159 7961
23562 76094
4507 80396
70329 91264
41532 61133
3580 43660
44...

result:

ok OK

Test #2:

score: 0
Accepted
time: 2471ms
memory: 20284kb

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
56815 52516
40377 1757
50463 66496
15833 50879
9828 16330
80692 9962
51095 17590
90774 57492
44786 41895
3386 35478
84803 93635
90745 34876
7472 34257
36580 19532
8821 61870
41395 2585
99666 33504
90496 2775
8128 71333
85506 34046
65629 62628
15022 71577
7538 82555
64524 72576
33208 93167
531...

result:

ok OK

Test #3:

score: 0
Accepted
time: 1ms
memory: 5448kb

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: 74ms
memory: 34716kb

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
25370 25370
415 415
16796 16796
12437 12437
22155 22155
84013 84013
37307 37307
72324 72324
83703 83703
78090 78090
9375 9375
82192 82192
74694 74694
49841 49841
15798 15798
36770 36770
27645 27645
50147 50147
73191 73191
47835 47835
80563 80563
22103 22103
12751 12751
24922 24922
15168 15168...

result:

ok OK

Test #5:

score: 0
Accepted
time: 59ms
memory: 34560kb

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
59469 59469
89516 89516
87040 87040
90184 90184
83075 83075
61454 61454
33615 33615
49725 49725
99247 99247
24121 24121
73533 73533
75845 75845
84418 84418
26636 26636
67341 67341
32504 32504
5752 5752
41749 41749
33184 33184
70841 70841
98815 98815
3265 3265
57647 57647
24293 24293
89920 899...

result:

ok OK

Test #6:

score: 0
Accepted
time: 2486ms
memory: 22396kb

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
22284 45795
58734 13903
57136 34144
7548 92850
27039 51542
69265 89381
67073 61392
86159 96135
83227 74827
86884 174
27268 94390
20020 55019
45357 92587
17833 7902
55801 46032
73310 23282
89482 60189
60485 28664
2721 48275
89892 7961
24437 76094
58192 80396
28938 91264
6101 61133
70994 43660
...

result:

ok OK

Test #7:

score: 0
Accepted
time: 2482ms
memory: 26940kb

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
4850 52516
69016 1757
85854 66496
48300 50879
83741 16330
98931 9962
38730 17590
81692 57492
5076 41895
23574 35478
61976 93635
96140 34876
64057 34257
25588 19532
99191 61870
73134 2585
60977 33504
67485 2775
79816 71333
35920 34046
16162 62628
89591 71577
91372 82555
96933 72576
92891 93167...

result:

ok OK

Test #8:

score: 0
Accepted
time: 122ms
memory: 18176kb

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
33247 33397
20397 20389
3730 3431
40713 40674
26106 25818
33018 33128
17364 17001
33979 34126
25258 25026
51002 51182
3467 3257
4615 4345
31121 31136
17105 16739
37181 37003
9414 8917
43414 43395
58110 58320
16045 15694
1286 1251
43494 43464
55702 55775
6451 6014
15976 15656
4614 4350
4367 406...

result:

ok OK

Test #9:

score: 0
Accepted
time: 108ms
memory: 16124kb

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
2493 2635
29001 29517
42481 42911
47086 47300
57204 56679
47023 47219
58952 58376
28914 29453
9637 9802
32481 33146
45305 45753
47248 47444
43315 43694
43804 44151
55644 55276
45490 45921
23721 24217
56266 55795
16283 16557
29367 29865
29554 30067
7754 8004
51233 51122
12439 12809
5051 5156
45...

result:

ok OK

Test #10:

score: 0
Accepted
time: 250ms
memory: 18940kb

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: 260ms
memory: 18772kb

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: 253ms
memory: 18808kb

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: 8ms
memory: 10092kb

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: 34ms
memory: 14660kb

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: 80ms
memory: 14244kb

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: 65ms
memory: 12536kb

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: 12ms
memory: 10388kb

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: 11076kb

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: 285ms
memory: 14764kb

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: 18ms
memory: 10912kb

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: 20ms
memory: 15664kb

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: 43ms
memory: 14912kb

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