QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#714106#9224. Express EvictionjimmyywangWA 2ms8108kbC++141.8kb2024-11-05 21:42:452024-11-05 21:42:47

Judging History

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

  • [2024-11-05 21:42:47]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:8108kb
  • [2024-11-05 21:42:45]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(ll i=a;i<=b;i++)
ll rd(){
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
#define d rd()
#define pb push_back
struct edge{ll u,v,w,nx;}e[200010];
ll cnt=1,hd[200020];
void add(ll u,ll v,ll w){e[++cnt]={u,v,w,hd[u]};hd[u]=cnt;}
void ad(ll u,ll v,ll w){add(u,v,w),add(v,u,0);}
ll n,m,S,T,nodes;
ll cur[100010];
ll dep[100010];
#define inf 0x3f3f3f3f3f3f3f3f
queue<ll>q;
bool bfs(){
	f(i,1,nodes)dep[i]=inf,cur[i]=hd[i];
	dep[S]=0;while(!q.empty())q.pop();
	q.push(S);while(!q.empty()){
		ll u=q.front();q.pop();
		for(int i=hd[u];i;i=e[i].nx){
			ll v=e[i].v;if(!e[i].w)continue;
			if(dep[v]==inf){
				dep[v]=dep[u]+1,q.push(v);
				if(v==T)return 1;
			}
		}
	}return 0;
}ll dfs(ll u,ll fl){
	if(u==T)return fl;
	ll sum=0;for(int i=cur[u];i&&fl;i=e[i].nx){
		ll v=e[i].v;cur[u]=i;if(!e[i].w||dep[v]!=dep[u]+1)continue;
		ll k=dfs(v,min(fl,e[i].w));
		fl-=k,sum+=k,e[i].w-=k,e[i^1].w+=k;
	}return sum;
}ll dinic(){
	ll res=0;while(bfs())res+=dfs(S,inf);
	return res;
}
char c[100][100];
ll ix[100][100],iy[100][100];
int main(){
    n=d,m=d;f(i,1,n)scanf("%s",c[i]+1);
    S=1,T=2;nodes=2;
    f(i,1,n)f(j,1,m)if(c[i][j]=='#'){
        ix[i][j]=++nodes,iy[i][j]=++nodes;
        if(j==1||(i==n&&j!=m))ad(S,ix[i][j],inf);
        if(i==1||(j==m&&i!=n))ad(iy[i][j],T,inf);
        ad(ix[i][j],iy[i][j],1);
    }f(i,1,n)f(j,1,m)if(c[i][j]=='#'){
        f(k,-2,2)f(l,-2,2){
            ll x=i+k,y=j+l;
            if(x<=0||y<=0||x>n||y>m||!ix[x][y])continue;
            ad(iy[i][j],ix[x][y],inf);
        }
    }cout<<dinic();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5760kb

input:

4 6
.##...
.#....
##....
....#.

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 8108kb

input:

20 30
...###########################
#..###########################
...###########################
...###########################
.#############################
...###########################
...###########################
#..###########################
...###########################
..#...............

output:

10

result:

wrong answer 1st numbers differ - expected: '11', found: '10'