QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#791657 | #898. 二分图最大匹配 | Mr_Min | TL | 230ms | 15200kb | C++14 | 888b | 2024-11-28 20:07:29 | 2024-11-28 20:07:30 |
Judging History
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 ...