QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#791657#898. 二分图最大匹配Mr_MinTL 230ms15200kbC++14888b2024-11-28 20:07:292024-11-28 20:07:30

Judging History

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

  • [2024-11-28 20:07:30]
  • 评测
  • 测评结果:TL
  • 用时:230ms
  • 内存:15200kb
  • [2024-11-28 20:07:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 1e5 + 5;
vector < int > g[N];
int l, r, m, mch[N], vis[N];
int dfs(int u, int t) {
  if (vis[u] == t) return 0;
  vis[u] = t;
  for (int v : g[u]) {
    if (!~mch[v] || dfs(mch[v], t)) return mch[v] = u, 1;
  }
  return 0;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> l >> r >> m;
  memset(mch, -1, sizeof(mch));
  memset(vis, -1, sizeof(vis));
  for (int i = 1, u, v; i <= m; i++) {
    cin >> u >> v;
    g[u].push_back(v);
  }
  int ret = 0;
  vector < int > ord(l);
  iota(ord.begin(), ord.end(), 0);
  mt19937 rng(random_device{}());
  shuffle(ord.begin(), ord.end(), rng);
  for (int i : ord) ret += dfs(i, i);
  cout << ret << '\n';
  for (int i = 0; i < r; i++) {
    if (~mch[i]) cout << mch[i] << ' ' << i << '\n';
  }
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 80ms
memory: 12692kb

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
63893 0
88633 1
96752 2
85610 3
94676 4
76685 5
31448 6
72044 7
70240 8
47175 9
43951 10
20110 11
30466 12
4229 13
46522 14
75223 15
62176 16
26851 17
78013 18
4961 19
85970 20
83385 21
99925 22
9079 23
99774 24
49446 25
97056 26
50528 27
24373 28
33211 29
47321 30
59580 31
78298 32
4755 33
9...

result:

ok OK

Test #2:

score: 0
Accepted
time: 82ms
memory: 14936kb

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
69205 0
60201 1
72021 2
5586 3
28931 4
95944 5
6919 6
54536 7
41523 8
21986 9
82162 10
3261 11
32139 12
82628 13
19581 14
53638 15
86118 16
55752 17
51052 18
29539 19
19938 20
88017 21
72427 22
50563 23
84262 24
96952 25
68293 26
77883 27
15925 28
17312 29
15316 30
64234 31
34238 32
21423 33
...

result:

ok OK

Test #3:

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

input:

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

output:

3
0 0
3 1
2 2

result:

ok OK

Test #4:

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

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: 53ms
memory: 11932kb

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: 84ms
memory: 13776kb

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
63893 0
88633 1
96752 2
85610 3
94676 4
76685 5
31448 6
72044 7
70240 8
47175 9
43951 10
20110 11
30466 12
4229 13
46522 14
75223 15
62176 16
26851 17
78013 18
4961 19
85970 20
83385 21
99925 22
9079 23
99774 24
49446 25
97056 26
50528 27
24373 28
33211 29
47321 30
59580 31
78298 32
4755 33
9...

result:

ok OK

Test #7:

score: 0
Accepted
time: 80ms
memory: 15200kb

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
69205 0
60201 1
72021 2
5586 3
28931 4
95944 5
6919 6
54536 7
41523 8
21986 9
82162 10
3261 11
32139 12
82628 13
19581 14
53638 15
86118 16
55752 17
51052 18
29539 19
19938 20
88017 21
72427 22
50563 23
84262 24
96952 25
68293 26
77883 27
15925 28
17312 29
15316 30
64234 31
34238 32
21423 33
...

result:

ok OK

Test #8:

score: 0
Accepted
time: 35ms
memory: 9044kb

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
0 0
16 1
14 2
17 3
15 4
11 5
13 6
19 9
18 10
20 11
21 12
12 13
26 14
28 15
30 20
34 22
31 28
32 29
35 31
33 35
42 38
39 39
44 40
41 44
45 45
36 46
49 51
57 52
54 53
50 54
61 55
66 57
70 61
71 63
64 65
85 67
86 69
83 71
80 72
79 73
84 74
87 75
90 76
91 77
88 78
101 79
96 80
107 85
126 95
112 96...

result:

ok OK

Test #9:

score: 0
Accepted
time: 37ms
memory: 8860kb

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 1
3 2
1 5
4 7
5 9
2 10
9 13
10 18
7 20
8 22
12 23
13 24
11 26
14 27
15 32
29 34
22 35
24 36
17 37
27 38
33 41
34 51
35 53
32 56
36 66
49 68
50 69
51 70
45 71
46 72
44 73
40 74
42 75
41 76
63 77
60 78
57 79
52 80
55 81
58 82
54 83
59 84
62 85
56 86
53 87
61 88
65 90
67 92
68 93
64 94
66 101
6...

result:

ok OK

Test #10:

score: 0
Accepted
time: 49ms
memory: 9560kb

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
76157 0
65007 2
98610 3
59447 4
10276 5
84441 6
37478 7
92005 8
1405 9
73602 10
52270 11
72508 12
66624 13
63974 14
72109 15
72713 16
30678 19
21513 20
3238 21
51898 22
99713 23
15921 24
83075 25
56662 26
60273 27
59508 28
17514 29
66636 30
64629 32
15429 33
73946 36
52951 37
23646 38
66061 39...

result:

ok OK

Test #11:

score: 0
Accepted
time: 45ms
memory: 9548kb

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
82146 0
30077 1
27728 2
51338 3
27221 4
12490 5
46579 7
25150 8
41196 9
21473 10
72897 11
22895 12
90231 14
97677 15
70086 16
52383 17
74250 18
4967 19
57484 20
40196 21
41188 22
73577 23
82437 24
45067 25
93408 26
6284 27
59289 28
99391 29
27964 30
29129 33
91962 36
22000 37
86449 38
22510 40...

result:

ok OK

Test #12:

score: 0
Accepted
time: 50ms
memory: 9584kb

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
2478 0
35662 1
71206 2
70671 3
38822 4
53831 5
13078 6
55324 7
10982 8
26149 9
32928 10
99017 11
8293 12
42753 14
61054 15
11064 16
50210 17
77368 18
40946 19
74055 20
949 21
77687 22
54360 23
65058 24
42816 25
3189 27
59146 28
78721 29
96941 30
75888 31
78258 32
53014 33
90333 34
54304 35
168...

result:

ok OK

Test #13:

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

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
16782 3
10594 17
15449 22
9963 25
16266 36
7859 40
10863 69
3123 73
17042 77
1258 84
5955 93
377 119
6511 123
10470 125
9666 127
8197 129
2186 131
10901 150
15655 161
13894 163
14912 166
17288 173
8753 176
15366 180
4382 181
5747 190
5104 195
4473 201
17663 202
5448 205
8087 214
3324 217
13348 ...

result:

ok OK

Test #14:

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

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
52721 0
29261 1
50603 2
66516 3
30071 4
52033 5
12896 6
10960 7
20841 8
26144 9
42237 10
55222 11
25691 12
38862 13
30351 14
49706 15
43369 16
21150 17
62255 18
54822 19
60954 20
18282 21
24246 22
32412 23
32408 24
26649 25
987 26
28093 27
7738 28
4066 29
10223 30
30439 31
68317 32
68528 33
64...

result:

ok OK

Test #15:

score: 0
Accepted
time: 19ms
memory: 8092kb

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
41527 3
11844 4
24751 5
42819 6
23940 8
26250 10
5843 11
16795 14
52402 15
21280 17
414 18
40946 19
13770 21
11098 22
7477 23
30592 24
41625 26
43924 28
8396 29
16465 30
41622 31
30595 32
17998 33
11671 34
6657 36
32852 37
42747 38
36516 39
5206 40
2508 41
43507 43
745 44
2255 45
41234 46
2464...

result:

ok OK

Test #16:

score: -100
Time Limit Exceeded

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:


result: