QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#810782 | #9224. Express Eviction | six-floor-slip-liu | WA | 0ms | 3764kb | C++20 | 2.9kb | 2024-12-12 11:01:33 | 2024-12-12 11:01:35 |
Judging History
answer
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=55,inf=0x3f3f3f3f;
int n,m,a[N][N];
char str[N];
namespace flow{
struct edge{
int v,rst,nxt;
}e[N*N*16];
int head[N*N*2],cur[N*N*2],dpt[N*N*2],cnte=1,s,t;
void adde(int u,int v,int w){
msg("%d %d %d|\n",u,v,w==1);
e[++cnte]=edge{v,w,head[u]};head[u]=cnte;
e[++cnte]=edge{u,0,head[v]};head[v]=cnte;
}
bool bfs(){
forup(i,1,t){
cur[i]=head[i];
dpt[i]=-1;
}
queue<int> q;
dpt[s]=0;
q.push(s);
while(q.size()){
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(!e[i].rst||dpt[v]!=-1) continue;
dpt[v]=dpt[u]+1;
q.push(v);
}
}
return ~dpt[t];
}
int dfs(int x,int flow){
if(x==t||!flow) return flow;
int res=0;
for(int &i=cur[x];i;i=e[i].nxt){
int v=e[i].v,rst=e[i].rst;
if(dpt[v]!=dpt[x]+1||!rst) continue;
int gt=dfs(v,min(flow-res,rst));
if(gt){
e[i].rst-=gt;
e[i^1].rst+=gt;
res+=gt;
if(res==flow) break;
}
}
return res;
}
int dinic(){
int ans=0;
while(bfs()){
ans+=dfs(s,inf);
}
return ans;
}
}
signed main(){
n=read();m=read();
forup(i,1,n){
scanf(" %s",str+1);
forup(j,1,m){
a[i][j]=(str[j]=='#');
}
}
flow::s=n*m*2+1;flow::t=flow::s+1;
forup(i,1,n){
forup(j,1,m){
int p=(i-1)*m+j,q=p+n*m;
if(i==n||j==1) flow::adde(flow::s,p,inf);
if(i==1||j==m) flow::adde(q,flow::t,inf);
if(!a[i][j]) flow::adde(p,q,1);
fordown(h,0,-2){
forup(w,0,2){
if(h==0&&w==0) continue;
int nx=i+h,ny=j+w;
if(nx<1||ny>m) continue;
int pn=(nx-1)*m+ny;
flow::adde(q,pn,inf);
}
}
}
}
printf("%d\n",flow::dinic());
}
/*
4 6
.##...
.#....
##....
....#.
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3764kb
input:
4 6 .##... .#.... ##.... ....#.
output:
7
result:
wrong answer 1st numbers differ - expected: '1', found: '7'