QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#810782#9224. Express Evictionsix-floor-slip-liuWA 0ms3764kbC++202.9kb2024-12-12 11:01:332024-12-12 11:01:35

Judging History

This is the latest submission verdict.

  • [2024-12-12 11:01:35]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3764kb
  • [2024-12-12 11:01:33]
  • Submitted

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'