QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#91566#898. 二分图最大匹配Minion#WA 2846ms31028kbC++231.7kb2023-03-29 07:26:422023-03-29 07:26:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-29 07:26:51]
  • 评测
  • 测评结果:WA
  • 用时:2846ms
  • 内存:31028kb
  • [2023-03-29 07:26:42]
  • 提交

answer

#include<cstdio>
#include<algorithm>
#define fo(i,x,y) for(int i = x;i <= y;++i)
#define fd(i,x,y) for(int i = x;i >= y;--i)
#define _is 1048576 * 10
#define gc() ib[++bi]
using namespace std;
char ib[_is];int bi = -1;
int rd()
{
	int x = 0;char ch = gc();
	while(ch < 48 || ch > 57) ch = gc();
	while(ch >= 48 && ch <= 57) x = x * 10 + ch - 48,ch = gc();
	return x;
}
int m,l,r,S,T,x,y;
int lst[200010],L[200010],d[200010],e[800010][2],tot = 1,Q[200010];
bool vs[200010],f[800010];
void add(int x,int y)
{
	e[++tot][0] = y,f[tot] = 1,e[tot][1] = lst[x],lst[x] = tot;
	e[++tot][0] = x,f[tot] = 0,e[tot][1] = lst[y],lst[y] = tot;
}
bool bfs()
{
	fo(i,0,T) vs[i] = 0;
	int st = 0,en = 1;Q[1] = S,vs[S] = 1;
	while(st < en)
	{
		int x = Q[++st];
		for(int i = lst[x];i;i = e[i][1])
		{
			int v = e[i][0];
			if(vs[v] == 0 && f[i]) vs[v] = 1,d[v] = d[x] + 1,Q[++en] = v;
		}
	}
	return vs[T];
}
#define min(x,y) (x < y ? x : y)
int dfs(int x,int fl)
{
	if(x == T || fl == 0) return fl;
	int F = 0;
	for(int &i = L[x];i;i = e[i][1])
	{
		int v = e[i][0];
		if((d[x] + 1) ^ d[v]) continue;
		int now = dfs(v,min(fl,f[i]));
		if(now <= 0) continue;
		f[i] -= now,f[i ^ 1] += now,F += now,fl -= now;
		if(fl == 0) break;
	}
	return F;
}
int main()
{
	fread(ib,1,_is,stdin);
	l = rd(),r = rd(),m = rd(),S = 0,T = l + r + 1;
	fo(i,1,l) add(S,i),add(i + l,T);
    fo(i,1,m) x = rd() + 1,y = rd() + 1,add(x,y + l);
	int ans = 0;
	while(bfs())
	{
		fo(i,0,T) L[i] = lst[i];
		ans += dfs(0,l);
	}
	printf("%d\n",ans);
    fo(i,1,l) for(int j = lst[i];j;j = e[j][1]) if(e[j][0] > l && f[j] == 0) {printf("%d %d\n",i - 1,e[j][0] - l - 1);break;}
}

详细

Test #1:

score: 100
Accepted
time: 2846ms
memory: 18672kb

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
0 54731
1 26066
2 89637
3 1717
4 68505
5 28330
6 55261
7 34703
8 42170
9 23249
10 90437
11 69580
12 72086
13 47593
14 29944
15 87183
16 763
17 2814
18 46044
19 75228
20 11487
21 72701
22 60611
23 36775
24 66081
25 45592
26 3321
27 88211
28 71467
29 47516
30 55528
31 83162
32 46298
33 26459
34...

result:

ok OK

Test #2:

score: 0
Accepted
time: 2790ms
memory: 17020kb

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
0 48685
1 54562
2 96282
3 43660
4 56572
5 72097
6 31793
7 12360
8 3023
9 14651
10 80163
11 12379
12 597
13 39076
14 77674
15 94527
16 85130
17 23849
18 35846
19 78842
20 26940
21 93329
22 69417
23 49345
24 65215
25 36147
26 45930
27 84619
28 76814
29 412
30 10858
31 38186
32 60852
33 64942
34...

result:

ok OK

Test #3:

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

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: 90ms
memory: 31028kb

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: 59ms
memory: 30096kb

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: 2458ms
memory: 17984kb

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
0 2401
1 18084
2 59700
3 99457
4 33291
5 38417
6 97167
7 64564
8 28471
9 68817
10 62095
11 31609
12 57675
13 28348
14 2599
15 99163
16 58923
17 17629
18 3975
19 53920
20 25930
21 4206
22 49364
23 55768
24 40573
25 87244
26 12858
27 39608
28 42953
29 68974
30 89214
31 48329
32 3980
33 50041
34...

result:

ok OK

Test #7:

score: 0
Accepted
time: 2447ms
memory: 24116kb

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
0 39785
1 26716
2 6189
3 33390
4 12388
5 6804
6 66264
7 36155
8 25212
9 73214
10 29914
11 87445
12 9428
13 44486
14 83326
15 61240
16 63409
17 15512
18 77732
19 17216
20 39374
21 7319
22 36983
23 45568
24 34087
25 31512
26 83824
27 73657
28 80853
29 58211
30 14867
31 17935
32 49451
33 91463
3...

result:

ok OK

Test #8:

score: -100
Wrong Answer
time: 116ms
memory: 12948kb

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:

37040
10 0
11 3
12 6
13 9
14 10
15 1
16 4
17 7
18 11
19 2
20 13
21 8
28 14
29 15
30 32
31 26
32 24
33 29
34 28
35 20
36 46
39 47
41 44
44 40
45 39
46 38
57 51
58 53
59 54
60 52
61 55
64 60
66 57
70 61
71 63
79 73
80 70
83 71
84 74
85 68
86 69
87 75
89 78
90 76
91 77
96 80
104 79
107 85
113 96
126 95...

result:

wrong answer # of Matching is differ - expected: '37154', found '37040'