QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91566 | #898. 二分图最大匹配 | Minion# | WA | 2846ms | 31028kb | C++23 | 1.7kb | 2023-03-29 07:26:42 | 2023-03-29 07:26:51 |
Judging History
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'