QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#586186 | #9224. Express Eviction | yyyyxh | WA | 1ms | 4188kb | C++14 | 2.3kb | 2024-09-24 08:25:19 | 2024-09-24 08:25:19 |
Judging History
answer
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N=53,INF=0x3f3f3f3f;
int n,m;
char s[N][N];
int id(int i,int j){
if(i&&i<=n&&j&&j<=m) return (i-1)*m+j;
return n*m+1;
}
namespace Net{
const int N=100003;
int n,s,t;
struct edge{
int u,v,w;
edge(){}
edge(int U,int V,int W):u(U),v(V),w(W){}
};
vector<edge> es,e;
void add(int u,int v,int w){
// printf("%d %d %d\n",u,v,w);
es.emplace_back(u,v,w);
es.emplace_back(v,u,0);
}
int buc[N],st[N],cur[N];
vector<int> op,loc;
void setedge(){
int len=es.size();
for(int i=0;i<len;++i) ++buc[es[i].u+1];
for(int i=1;i<=n+1;++i) buc[i]+=buc[i-1],st[i]=buc[i];
e.resize(len);op.resize(len);loc.resize(len);
for(int i=0;i<len;++i) e[loc[i]=buc[es[i].u]++]=es[i];
for(int i=0;i<len;++i) op[loc[i]]=loc[i^1];
es=e;
}
int que[N],tl;
int dis[N];
bool bfs(){
for(int i=1;i<=n;++i) dis[i]=-1,cur[i]=st[i];
dis[que[tl=1]=s]=0;
for(int pos=1;pos<=tl;++pos){
int u=que[pos];
for(int i=st[u];i<st[u+1];++i){
if(!e[i].w) continue;
int v=e[i].v;
if(~dis[v]) continue;
dis[que[++tl]=v]=dis[u]+1;
}
}
return ~dis[t];
}
int dfs(int u,int fl){
if(u==t||!fl) return fl;
int sum=0;
for(int i=cur[u];i<st[u+1]&&fl;++i){
cur[u]=i;
if(!e[i].w) continue;
int v=e[i].v;
if(dis[v]!=dis[u]+1) continue;
int t=dfs(v,min(e[i].w,fl));
fl-=t;e[i].w-=t;e[op[i]].w+=t;sum+=t;
}
return sum;
}
int flow(){
int res=0;
while(bfs()) res+=dfs(s,INF);
return res;
}
}
int main(){
scanf("%d%d",&n,&m);
Net::n=2*n*m+2;Net::s=2*n*m+2;Net::t=2*n*m+1;
for(int i=1;i<=n;++i){
scanf("%s",s[i]+1);
reverse(s[i]+1,s[i]+m+1);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(s[i][j]=='#') Net::add(2*id(i,j)-1,2*id(i,j),1);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(s[i][j]=='#'){
for(int a=i;a<=i+2&&a<=n;++a)
for(int b=j;b<=j+2&&b<=m;++b)
if(a-i+b-j>=1&&s[a][b]=='#') Net::add(2*id(i,j),2*id(a,b)-1,INF);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
if((i==1||j==1)&&(s[i][j]=='#')) Net::add(Net::s,2*id(i,j)-1,INF);
if((i==n||j==m)&&(s[i][j]=='#')) Net::add(2*id(i,j),Net::t,INF);
}
Net::setedge();
printf("%d\n",Net::flow());
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3920kb
input:
4 6 .##... .#.... ##.... ....#.
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 4188kb
input:
20 30 ...########################### #..########################### ...########################### ...########################### .############################# ...########################### ...########################### #..########################### ...########################### ..#...............
output:
10
result:
wrong answer 1st numbers differ - expected: '11', found: '10'