QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#586186#9224. Express EvictionyyyyxhWA 1ms4188kbC++142.3kb2024-09-24 08:25:192024-09-24 08:25:19

Judging History

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

  • [2024-09-24 08:25:19]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4188kb
  • [2024-09-24 08:25:19]
  • 提交

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'