QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#714106 | #9224. Express Eviction | jimmyywang | WA | 2ms | 8108kb | C++14 | 1.8kb | 2024-11-05 21:42:45 | 2024-11-05 21:42:47 |
Judging History
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;
}
详细
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'