QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#136589#5202. DominoesOccDreamerWA 1191ms22372kbC++143.1kb2023-08-09 09:12:192023-08-09 09:12:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-09 09:12:22]
  • 评测
  • 测评结果:WA
  • 用时:1191ms
  • 内存:22372kb
  • [2023-08-09 09:12:19]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

const int inf = 1e9;
const int MAXN = 1e6+6;
const int rx[]={1,-1,0,0}, ry[]={0,0,1,-1};

int S, T;
int n, m, cnt=1, tot, col[3], mch[MAXN], c[MAXN];
int head[MAXN], cur[MAXN], de[MAXN], hd, tl, Q[MAXN], ne[MAXN<<1], to[MAXN<<1], weight[MAXN<<1], idx[1002][1002];

char s[1002][1002];

bool mark[MAXN];

inline bool paint(int x, int y){return (x+y)&1;}

inline void reset(){
	for(int i=2;i<cnt;i+=2) weight[i]+=weight[i^1], weight[i^1
	]=0;
	return ; 
}

inline void add(int x, int y, int w){++cnt;to[cnt]=y;ne[cnt]=head[x];head[x]=cnt;weight[cnt]=w;}

inline void addedge(int x, int y, int w){add(x,y,w), add(y,x,0);}

inline int dinic(int now, int flow){
	if(now==T) return flow;
	int maxnflow=0, res;
	for(int i=cur[now];i && flow;i=ne[i]){
		cur[now]=i;
		if(de[to[i]]==de[now]+1 && weight[i]){
			res=dinic(to[i],min(flow,weight[i]));
			weight[i]-=res, weight[i^1]+=res;
			maxnflow+=res, flow-=res;
		}
	}
	return maxnflow;
}	

inline bool bfs(int limit=-1){
	Q[hd=tl=1]=S; de[S]=1;
	for(int i=1;i<=T;++i) de[i]=0;
	while(hd<=tl){
		int t=Q[hd++];
		cur[t]=head[t];
		if(t==T) return 1;
		for(int i=head[t];i;i=ne[i])
			if(weight[i] && de[to[i]]==0 && to[i]!=limit) de[to[i]]=de[t]+1, Q[++tl]=to[i];	
	}
	return 0;
}

inline int solve(int x){
	reset(); int res=0;
	while(bfs(x)) res+=dinic(S,inf);
	int p=tot>>1, cc;
	if(res<p-1) return 0;
	for(int i=1;i<=tot;++i) mch[i]=0; 
	for(int i=1;i<=tot;++i){
		if(c[i] && i!=x){
			for(int j=head[i];j;j=ne[j]){
				if(to[j]==S || weight[j] || to[j]==x) continue;
				mch[to[j]]=i; mch[i]=to[j]; break;
			}
		}
		mark[i]=0;
	}
	for(int i=1;i<=tot;++i) if(mch[i]==0 && i!=x) cc=i;
	int co=0;
	Q[hd=tl=1]=cc; mark[cc]=1;
	while(hd<=tl){
		int t=Q[hd++]; co++;
		//cerr << "bfs:" << t << endl;
		for(int i=head[t];i;i=ne[i]){
			if(to[i]==S || to[i]==T || to[i]==x) continue;
			//cerr << to[i] << ' ' << mch[to[i]] << endl;
			if(mark[mch[to[i]]]) continue;
			mark[mch[to[i]]]=1; Q[++tl]=mch[to[i]];
		}
	}
	//cerr << "co=" << co << endl;
	return co;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j){
			if(s[i][j]=='#') continue;
			//s[i][j]='.';
			col[paint(i,j)]++; idx[i][j]=++tot; c[tot]=paint(i,j);
			if(tot>2000) break;
		}
	if(tot&1) return printf("%lld",min(999000ll,1ll*tot*(tot-1)/2)), 0;
	if(col[0]+col[1]>=2000) return printf("1000000"), 0; S=0, T=tot+1;
	int ans=0, x, y;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(s[i][j]=='#') continue;
			if(paint(i,j)){
				addedge(S,idx[i][j],1);
				for(int k=0;k<4;++k){
					x=i+rx[k], y=j+ry[k];
					if(x>=1 && x<=n && y>=1 && y<=m && s[x][y]!='#') addedge(idx[i][j],idx[x][y],1);
				}	
			}
			else addedge(idx[i][j],T,1);
		}
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(s[i][j]!='#') ans+=solve(idx[i][j]);
	printf("%d",min(999000,tot*(tot-1)/2-ans/2));
	return 0;
}
/*
3 7
...#...
...#...
...#...
*/

























詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 22100kb

input:

3 6
...#..
......
#...##

output:

52

result:

ok 1 number(s): "52"

Test #2:

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

input:

2 2
..
..

output:

2

result:

ok 1 number(s): "2"

Test #3:

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

input:

2 2
#.
#.

output:

0

result:

ok 1 number(s): "0"

Test #4:

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

input:

4 5
###..
.###.
.##..
#...#

output:

34

result:

ok 1 number(s): "34"

Test #5:

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

input:

11 12
.#######..##
.##..#.....#
#####..##.#.
#..##...#...
###..#..##..
####..###...
.#....##..##
.#####....##
.###..######
.######...##
#....##...##

output:

1674

result:

ok 1 number(s): "1674"

Test #6:

score: 0
Accepted
time: 63ms
memory: 22372kb

input:

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

output:

496312

result:

ok 1 number(s): "496312"

Test #7:

score: 0
Accepted
time: 348ms
memory: 22148kb

input:

34 65
...............#####.#..##..############.....###....#..##########
.........#......#.......##..############.##..##........##########
..............#.......#.....##########..............##.##########
...##............#..............######.......#......#..##########
......#....#.....##......#.......

output:

279744

result:

ok 1 number(s): "279744"

Test #8:

score: 0
Accepted
time: 1191ms
memory: 22068kb

input:

44 44
............................................
............................................
............................................
............................................
............................................
............................................
...........................

output:

936056

result:

ok 1 number(s): "936056"

Test #9:

score: -100
Wrong Answer
time: 2ms
memory: 7912kb

input:

45 45
.............................................
.............................................
.............................................
.............................................
.............................................
.............................................
.....................

output:

1000000

result:

wrong answer 1st numbers differ - expected: '999000', found: '1000000'