QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#676255#898. 二分图最大匹配Poetry#TL 140ms15852kbC++23837b2024-10-25 20:48:152024-10-25 20:48:15

Judging History

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

  • [2024-10-25 20:48:15]
  • 评测
  • 测评结果:TL
  • 用时:140ms
  • 内存:15852kb
  • [2024-10-25 20:48:15]
  • 提交

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...

output:


result: