QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#676255 | #898. 二分图最大匹配 | Poetry# | TL | 140ms | 15852kb | C++23 | 837b | 2024-10-25 20:48:15 | 2024-10-25 20:48:15 |
Judging History
answer
#include <bits/stdc++.h>
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
constexpr int N = 1E5 + 5;
int L, R, m, bel[N];
int vis[N];
std::vector<int> adj[N];
int dfs(int x, int i) {
if (vis[x] == i) return 0;
vis[x] = i;
for (auto v : adj[x]) {
if (!bel[v] || dfs(bel[v], i)) {
bel[v] = x;
return 1;
}
}
return 0;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> L >> R >> m;
for (int i = 1; i <= m; ++i) {
int u, v;
std::cin >> u >> v;
++u, ++v;
adj[u].push_back(v);
}
int ans = 0;
for (int i = 1; i <= L; ++i) {
ans += dfs(i, i);
}
std::cout << ans << "\n";
for (int i = 1; i <= R; ++i) {
if (bel[i]) std::cout << bel[i] - 1 << " " << i - 1 << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 140ms
memory: 15852kb
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 12041 0 72487 1 5283 2 69829 3 42164 4 90712 5 92014 6 59953 7 71269 8 58488 9 96208 10 72327 11 57264 12 60846 13 52381 14 59008 15 50389 16 35924 17 32625 18 21527 19 27578 20 47990 21 90601 22 76846 23 36019 24 21960 25 56983 26 38043 27 92270 28 25033 29 16929 30 23472 31 49575 32 77052 3...
result:
ok OK
Test #2:
score: 0
Accepted
time: 123ms
memory: 12156kb
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: 1ms
memory: 3576kb
input:
4 4 7 1 1 2 2 0 0 3 1 1 2 2 0 3 2
output:
3 0 0 1 1 2 2
result:
ok OK
Test #4:
score: -100
Time Limit Exceeded
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...