QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #113431 | #6546. Greedy Bipartite Matching | vme50 | WA | 55ms | 10032kb | C++17 | 1.5kb | 2023-06-17 18:23:03 | 2023-06-17 18:23:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define N 200005
#define M 1000005
#define pb push_back
int n,m,c,q[N],dst[N],mch[N],ans[N];bool vs[N];bitset<N> tg,tg1;
int cntE,hd[N];struct Edge {int v,pr,sf;}e[M];
void addE(int u,int v) {e[++cntE]=(Edge) {v,0,hd[u]};e[hd[u]].pr=cntE;hd[u]=cntE;}
void dltE(int u,int x)
{if(x==hd[u]) hd[u]=e[x].sf;else e[e[x].pr].sf=e[x].sf,e[e[x].sf].pr=e[x].pr;}
bool bfs()
{
bool fl=0;fill(vs+1,vs+n+1,0);fill(dst+1,dst+n+1,-1);q[0]=2;q[1]=1;
for(int i=1;i<=n;++i) if(!mch[i]) dst[i]=0,q[++q[1]]=i;
while(q[0]<=q[1])
{
int u=q[q[0]++];
for(int i=hd[u],v;i;i=e[i].sf)
{
v=e[i].v;
if(mch[v]) {v=mch[v];if(dst[v]==-1) dst[v]=dst[u]+1,q[++q[1]]=v;}
else fl=1;
}
}return fl;
}
bool dfs(int u)
{
if(!u) return 1;if(vs[u]) return 0;vs[u]=1;
for(int i=hd[u],v;i;i=e[i].sf)
{
v=e[i].v;
if((!mch[v] || dst[mch[v]]==dst[u]+1) && dfs(mch[v]))
{mch[u]=v;mch[v]=u;return 1;}
}return 0;
}
void slv(int x)
{
tg=0;while(bfs()) for(int i=1;i<=n;++i) if(!vs[i]) ans[x]+=dfs(i);bfs();
for(int i=1;i<=n;++i) if(~dst[i]) for(int j=hd[i],v;j;j=e[j].sf)
{v=e[j].v;if(mch[i]!=v) tg[v]=1;}else tg[i]=1;
for(int i=1;i<=n;++i) if(tg[i]) for(int j=hd[i],v;j;j=e[j].sf)
{v=e[j].v;if(tg[v]) dltE(i,j);}tg1|=tg;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;++i)
{
scanf("%d",&c);
for(int j=1,u,v;j<=c;++j)
{scanf("%d %d",&u,&v);if(!tg1[u] && !tg1[n+v]) addE(u,n+v);}slv(i);
}for(int i=1;i<=m;++i) ans[i]+=ans[i-1],printf("%d ",ans[i]);return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3708kb
input:
3 4 2 1 1 1 2 2 1 1 2 2 2 1 3 3 2 1 3 3
output:
1 2 2 3
result:
ok 4 number(s): "1 2 2 3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3428kb
input:
0 0
output:
result:
ok 0 number(s): ""
Test #3:
score: 0
Accepted
time: 2ms
memory: 7732kb
input:
2 2 0 2 1 2 1 2
output:
0 1
result:
ok 2 number(s): "0 1"
Test #4:
score: 0
Accepted
time: 39ms
memory: 9660kb
input:
100000 1 200000 78475 45796 32145 46393 92550 13904 73461 34145 96461 92851 56319 77067 77530 84437 76343 51543 77507 99269 76411 89382 1779 61393 43608 96136 84269 74828 14858 35967 32085 94909 19877 175 1482 94391 12424 55020 64369 92588 81296 7903 25433 46033 36294 61129 73556 84837 8419 10215 12...
output:
100000
result:
ok 1 number(s): "100000"
Test #5:
score: 0
Accepted
time: 42ms
memory: 9224kb
input:
100000 1 200000 56816 52517 2577 76202 40378 1758 50464 66497 15834 50880 9829 16331 80693 9963 51096 17591 15871 35192 91302 65510 90775 57493 11891 8967 44787 41896 3387 35479 93471 47453 84804 93636 90746 34877 18202 38718 7473 34258 36581 19533 13249 27525 6442 69870 8822 61871 94537 67714 41396...
output:
100000
result:
ok 1 number(s): "100000"
Test #6:
score: 0
Accepted
time: 2ms
memory: 5744kb
input:
4 1 7 2 2 3 3 1 1 4 2 2 3 3 1 4 3
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 26ms
memory: 9480kb
input:
100000 1 199999 25371 25371 85965 85964 416 416 16797 16797 12438 12438 45410 45409 63006 63005 22156 22156 87829 87828 84014 84014 37308 37308 72325 72325 83704 83704 55391 55390 6781 6780 78091 78091 9376 9376 82193 82193 74695 74695 49842 49842 15799 15799 69856 69855 82949 82948 97390 97389 205 ...
output:
100000
result:
ok 1 number(s): "100000"
Test #8:
score: 0
Accepted
time: 30ms
memory: 10032kb
input:
100000 1 199999 59470 59470 76774 76773 89517 89517 87041 87041 90185 90185 83076 83076 61455 61455 33616 33616 85795 85794 92073 92072 49726 49726 63843 63842 99248 99248 24122 24122 29553 29552 73534 73534 75846 75846 27030 27029 84419 84419 26637 26637 10101 10100 75014 75013 67342 67342 75647 75...
output:
100000
result:
ok 1 number(s): "100000"
Test #9:
score: 0
Accepted
time: 41ms
memory: 9340kb
input:
100000 1 199999 22285 45796 32145 44931 58735 13904 57137 34145 7549 92851 56319 11875 77530 85279 27040 51543 77507 94258 69266 89382 67074 61393 86160 96136 83228 74828 14858 19501 32085 73640 86885 175 27269 94391 20021 55020 45358 92588 17834 7903 55802 46033 36294 46558 73556 13747 8419 88394 1...
output:
100000
result:
ok 1 number(s): "100000"
Test #10:
score: 0
Accepted
time: 41ms
memory: 9692kb
input:
100000 1 199999 4851 52517 2577 29251 69017 1758 85855 66497 48301 50880 83742 16331 98932 9963 38731 17591 15871 13961 91302 97596 81693 57493 11891 59333 5077 41896 23575 35479 93471 65246 61977 93636 96141 34877 18202 35367 64058 34258 25589 19533 13249 91004 6442 83449 99192 61871 94537 16903 73...
output:
100000
result:
ok 1 number(s): "100000"
Test #11:
score: -100
Wrong Answer
time: 55ms
memory: 9464kb
input:
100000 1 199997 4415 9894 97824 23182 2551 30097 24322 27913 64552 31862 23073 68076 28494 14953 11400 33367 14514 13085 40869 51446 63170 88054 76550 23848 22657 57759 9479 56985 96440 59224 69954 84962 55443 22220 96520 87619 31746 72821 8800 6061 36912 77572 8970 95816 32991 68335 29931 84159 333...
output:
63503
result:
wrong answer 1st numbers differ - expected: '63398', found: '63503'