QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#810785#9224. Express Evictionsix-floor-slip-liuWA 1ms3920kbC++202.8kb2024-12-12 11:02:282024-12-12 11:02:35

Judging History

This is the latest submission verdict.

  • [2024-12-12 11:02:35]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3920kb
  • [2024-12-12 11:02:28]
  • 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){
        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: 100
Accepted
time: 1ms
memory: 3812kb

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3920kb

input:

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

output:

10

result:

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