QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#588332#9224. Express EvictionDisplace_RE 4ms4828kbC++142.2kb2024-09-25 09:40:092024-09-25 09:40:10

Judging History

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

  • [2024-09-25 09:40:10]
  • 评测
  • 测评结果:RE
  • 用时:4ms
  • 内存:4828kb
  • [2024-09-25 09:40:09]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mapa make_pair
typedef long double ld;
typedef unsigned long long ull;
template <typename T>inline void read(T &x){
	x=0;char c=getchar();bool f=0;
	for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}
const int N=100000, inf=1e9;
int n, m;
char s[55][55];
int id[55][55][2], idx, S, T;
int lin[N], nxt[N], to[N], fl[N], tot=1;
inline void in(int x, int y, int z){
	nxt[++tot]=lin[x]; lin[x]=tot; to[tot]=y; fl[tot]=z;
	nxt[++tot]=lin[y]; lin[y]=tot; to[tot]=x; fl[tot]=0;
}
int dep[N], cur[N];
inline bool bfs(){
	for(int i=1; i<=T; ++i) dep[i]=0, cur[i]=0;
	dep[S]=1; cur[S]=lin[S];
	queue<int> que;
	que.emplace(S);
	while(!que.empty()){
		int x=que.front(); que.pop();
		for(int i=lin[x]; i; i=nxt[i]){
			int y=to[i];
			if(fl[i]&&(!dep[y])){
				dep[y]=dep[x]+1; cur[y]=lin[y]; 
				if(y==T) return true;
				que.emplace(y);
			}
		}
	}
	return false;
}
inline int dfs(int x, int now){
	if(x==T) return now;
	int ret=0;
	for(int i=cur[x]; i&&ret<now; i=nxt[i]){
		cur[x]=i;
		int y=to[i];
		if(fl[i]&&dep[y]==dep[x]+1){
			int res=dfs(y, min(fl[i], now-ret));
			fl[i]-=res; fl[i^1]+=res; ret+=res;
		}
	}
	return ret;
}
int mxfl;
int main(){
	// freopen("D:\\nya\\acm\\C\\test.in","r",stdin);
	// freopen("D:\\nya\\acm\\C\\test.out","w",stdout);
	read(n); read(m);
	for(int i=1; i<=n; ++i){
		scanf("%s", s[i]+1);
		for(int j=1; j<=m; ++j) id[i][j][0]=++idx, id[i][j][1]=++idx;
	}
	S=idx+1; T=idx+2;
	for(int i=1; i<=n; ++i) in(S, id[i][1][0], inf), in(id[i][m][1], T, inf);
	for(int j=1; j<=m; ++j) in(id[1][j][1], T, inf), in(S, id[n][j][0], inf);
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) in(id[i][j][0], id[i][j][1], s[i][j]=='#');
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j){
		for(int ii=1; ii<=n; ++ii) for(int jj=1; jj<=m; ++jj){
			if(abs(ii-i)<=2&&abs(jj-j)<=2) in(id[i][j][1], id[ii][jj][0], inf);
		}
	}
	while(bfs()){
		int fl=dfs(S, inf);
		while(fl) mxfl+=fl, fl=dfs(S, inf);
	}
	printf("%d\n", mxfl);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3728kb

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 4156kb

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #3:

score: 0
Accepted
time: 4ms
memory: 4828kb

input:

35 35
....###########...#########........
##..#######################..#####.
....#######################..#####.
...#.....##################..#####.
.##......##################.....##.
.##..##..#############.....#....##.
.....##..#############......##..##.
....#....#############..##..##..##.
####.....

output:

16

result:

ok 1 number(s): "16"

Test #4:

score: 0
Accepted
time: 1ms
memory: 4192kb

input:

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

output:

5

result:

ok 1 number(s): "5"

Test #5:

score: -100
Runtime Error

input:

50 45
...##................##...................#..
...#......#.#..........#.#.....####....#....#
....#.....#..............#..#..##......##..#.
.....#......######........#.............#....
......##...#...##...##.......#....#..#...##..
...#..##.....##...###.............#..##.....#
...#......########...

output:


result: