QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#561000 | #9224. Express Eviction | Afterlife# | WA | 0ms | 39592kb | C++17 | 2.6kb | 2024-09-12 19:24:52 | 2024-09-12 19:24:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1e3+7;
struct Edge{
int ne,to,w;
}edg[N*2+1];
int cnt=1,head[N],hd[N];
void build(int u,int v,int w)
{
++cnt;
edg[cnt].to=v;
edg[cnt].ne=head[u];
edg[cnt].w=w;
head[u]=cnt;
++cnt;
edg[cnt].to=u;
edg[cnt].ne=head[v];
edg[cnt].w=0;
head[v]=cnt;
}
queue<int> q;
int d[N],S,T;
bool bfs()
{
fill(d+S,d+T+1,-1);
d[S]=0;
q.push(S);
while(!q.empty())
{
int x=q.front();
q.pop();
hd[x]=head[x];
for(int tmp=head[x];tmp;tmp=edg[tmp].ne)
{
int v=edg[tmp].to;
if(d[v]!=-1||!edg[tmp].w)
continue;
d[v]=d[x]+1;
q.push(v);
}
}
return d[T]!=-1;
}
int dinic(int x,int mn)
{
if(!mn||x==T)
return mn;
int flow=0,tmpf;
for(int &tmp=hd[x];tmp;tmp=edg[tmp].ne)
{
int v=edg[tmp].to;
if(d[v]==d[x]+1&&(tmpf=dinic(v,min(mn,edg[tmp].w)))>0)
{
flow+=tmpf;
mn-=tmpf;
edg[tmp].w-=tmpf;
edg[tmp^1].w+=tmpf;
}
if(!mn)
break;
}
return flow;
}
int n,m;
string s[N];
int gid(int x,int y,int i)
{
return (x-1)*m+y+(i-1)*n*m;
}
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
S=0,T=n*m*4+1;
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[i]=' '+s[i];
}
//1:in 2:out 3:(0) 4:(1)
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
build(gid(i,j,1),gid(i,j,2),1e9);
build(gid(i,j,2),gid(i,j,3),1e9);
build(gid(i,j,3),gid(i,j,4),s[i][j]=='#');
build(gid(i,j,4),gid(i,j,1),1e9);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int d=0;d<4;d++)
{
int k=i+dx[d],l=j+dy[d];
if(k<1||k>n||l<1||l>m)
continue;
build(gid(i,j,2),gid(k,l,3),1e9);
build(gid(i,j,4),gid(k,l,1),1e9);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(s[i][j]!='#')
continue;
if(j==1||i==n)
build(S,gid(i,j,3),1e9);
if(j==m||i==1)
build(gid(i,j,4),T,1e9);
}
int ans=0;
while(bfs())
ans+=dinic(S,1e9);
cout<<ans<<"\n";
}
/*
6 4
..#.
###.
#...
....
...#
....
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 39572kb
input:
4 6 .##... .#.... ##.... ....#.
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 39592kb
input:
20 30 ...########################### #..########################### ...########################### ...########################### .############################# ...########################### ...########################### #..########################### ...########################### ..#...............
output:
7
result:
wrong answer 1st numbers differ - expected: '11', found: '7'