QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#270956#7733. Cool, It’s Yesterday Four Times Moreucup-team134#WA 1ms7940kbC++141.4kb2023-12-01 18:53:052023-12-01 18:53:07

Judging History

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

  • [2023-12-01 18:53:07]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7940kb
  • [2023-12-01 18:53:05]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ull uint64_t
mt19937_64 rng(time(0));

const int N=1050;
char s[N][N];
ull hsh[N][N];

vector<pair<int,int>> pts;
bool was[N][N];
int n,m;
int mv[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

void DFS(int x,int y){
	pts.pb({x,y});
	was[x][y]=true;
	for(int i=0;i<4;i++){
		int X=x+mv[i][0];
		int Y=y+mv[i][1];
		if(X>=1 && X<=n && Y>=1 && Y<=m && s[X][Y]=='.' && !was[X][Y]){
			DFS(X,Y);
		}
	}
}

int main(){
	int t;
	scanf("%i",&t);
	while(t--){
		scanf("%i %i",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%s",s[i]+1);
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				hsh[i][j]=rng();
			}
		}
		int sz=0;
		map<pair<int,ll>,int> cnt;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(s[i][j]=='.' && !was[i][j]){
					pts.clear();
					DFS(i,j);
					ull h=0;
					int mnx=n,mny=m;
					for(auto p:pts){
						mnx=min(mnx,p.first);
						mny=min(mny,p.second);
					}
					for(auto p:pts){
						h^=hsh[p.first-mnx][p.second-mny];
					}
					cnt[{(int)pts.size(),h}]++;
					sz=max(sz,(int)pts.size());
				}
			}
		}
		int ans=0;
		for(auto it:cnt){
			if(it.first.first==sz){
				if(it.second==1){
					ans+=sz;
				}
			}
		}
		printf("%i\n",ans);

		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				was[i][j]=false;
			}
		}
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7940kb

input:

4
2 5
.OO..
O..O.
1 3
O.O
1 3
.O.
2 3
OOO
OOO

output:

3
1
0
0

result:

ok 4 lines

Test #2:

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

input:

200
2 4
OOO.
OO..
2 3
OOO
.O.
3 3
O.O
OOO
OO.
4 1
.
.
O
O
1 2
.O
1 1
.
2 5
.OO..
.O.O.
2 1
O
O
1 1
O
1 3
.OO
5 1
O
O
.
O
.
5 2
O.
..
O.
.O
..
5 3
...
...
.OO
..O
OOO
3 5
..O.O
.O.O.
.OO.O
5 2
.O
OO
O.
O.
..
2 1
O
O
3 5
.O.OO
O...O
..OO.
1 5
.....
5 1
O
.
O
.
.
5 3
OOO
OO.
.OO
OO.
O.O
2 1
O
.
5 2
O.
...

output:

3
0
0
2
1
1
3
0
0
1
0
4
9
4
4
0
6
5
2
0
1
6
4
5
2
0
0
5
3
3
1
4
1
0
4
5
2
3
7
3
0
6
2
2
2
0
4
6
6
3
3
2
3
3
2
1
0
3
3
4
4
2
2
0
7
6
4
8
5
3
2
5
2
1
2
1
4
0
0
2
5
1
4
6
6
1
6
2
2
3
4
5
2
1
0
1
9
3
4
11
0
3
2
1
0
0
4
3
1
4
3
8
3
0
3
6
2
3
1
3
3
4
0
2
11
2
2
4
0
4
4
6
2
1
2
3
0
5
0
16
4
3
2
6
0
8
3
3
1...

result:

wrong answer 12th lines differ - expected: '7', found: '4'