QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#372258#8507. Clever Cell ChoicesYeongTreeWA 2ms8600kbC++173.1kb2024-03-31 08:00:092024-03-31 08:00:11

Judging History

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

  • [2024-03-31 08:00:11]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:8600kb
  • [2024-03-31 08:00:09]
  • 提交

answer

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <set>
#include <map>
#include <random>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define plll pair<long long, pll>
#define tiii array<int, 3>
#define tiiii array<int, 4>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
typedef long long ll;
const int INF = (int)1e9 + 7;

using namespace std;

int N = 0, M = 0;
vector<int> gph[101010];
vector<int> rgph[101010];
int A[101010];
int B[101010];
int D[101010];
int pt[101010];

bool dfs(int x)
{
	for(; pt[x] < (int)gph[x].size(); ++pt[x])
	{
		int y = gph[x][pt[x]];
		if(B[y] == -1 || (D[x] + 1 == D[B[y]] && dfs(B[y])))
		{
			A[x] = y;
			B[y] = x;
			return true;
		}
	}
	return false;
}

bool bfs(void)
{
	fill(D, D + N, -1);
	fill(pt, pt + N, 0);
	queue<int> Q;
	for(int i = 0; i < N; ++i) if(A[i] == -1) D[i] = 0, Q.push(i);

	bool ret = false;
	while(Q.size())
	{
		int x = Q.front(); Q.pop();
		for(auto y : gph[x])
		{
			if(B[y] == -1) return true;
			else if(D[B[y]] == -1) D[B[y]] = D[x] + 1, Q.push(B[y]);
		}
	}

	return false;
}

int match()
{
	int ret = 0;
	while(bfs()) for(int i = 0; i < N; ++i) if(A[i] == -1 && dfs(i)) ++ret;
	return ret;
}

int pA[101010];
int pB[101010];

int solA(int x)
{
	if(pA[x] != -1) return pA[x];
	pA[x] = 0;
	for(auto y : rgph[A[x]]) if(solA(y)) return pA[x] = 1;
	return pA[x] = 0;
}

int solB(int x)
{
	if(pB[x] != -1) return pB[x];
	pB[x] = 0;
	for(auto y : gph[B[x]]) if(solB(y)) return pB[x] = 1;
	return pB[x] = 0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m; cin >> n >> m;
	string str[n];
	for(auto &i : str) cin >> i;

	int chc[n][m];
	fill(*chc, *chc + n * m, -1);
	for(int i = 0; i < n; ++i)
	{
		for(int j = 0; j < m; ++j) if(str[i][j] == '.')
		{
			if(i + j & 1) chc[i][j] = N++;
			else chc[i][j] = M++;
		}
	}

	for(int i = 0; i < n; ++i)
	{
		for(int j = 0; j < m; ++j) if(str[i][j] == '.')
		{
			if(i + j & 1)
			{
				for(int t = 0; t < 4; ++t)
				{
					int dx = i + "0211"[t] - '1';
					int dy = j + "1102"[t] - '1';
					if(dx >= 0 && dy >= 0 && dx < n && dy < m && str[dx][dy] == '.') 
					{
						gph[chc[i][j]].push_back(chc[dx][dy]);
						rgph[chc[dx][dy]].push_back(chc[i][j]);
					}
				}
			}
		}
	}

	// cout << "ok" << endl;

	fill(A, A + N, -1);
	fill(B, B + M, -1);
	match();
	
	// cout << "ok" << endl;

	// cout << N << ' ' << M << '\n';
	// for(int i = 0; i < N; ++i) cout << A[i] << ' '; cout << '\n';
	// for(int i = 0; i < M; ++i) cout << B[i] << ' '; cout << '\n';

	fill(pA, pA + N, -1);
	fill(pB, pB + M, -1);
	for(int i = 0; i < N; ++i) if(A[i] == -1) pA[i] = 1;
	for(int i = 0; i < M; ++i) if(B[i] == -1) pB[i] = 1;
	for(int i = 0; i < N; ++i) if(pA[i] == -1) solA(i);
	for(int i = 0; i < M; ++i) if(pB[i] == -1) solB(i);

	int ans = 0;
	for(int i = 0; i < N; ++i) if(pA[i] == 1) ++ans;
	for(int i = 0; i < M; ++i) if(pB[i] == 1) ++ans;
	cout << ans;
}

详细

Test #1:

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

input:

3 3
#.#
...
#.#

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 2ms
memory: 8584kb

input:

3 3
..#
...
...

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 2ms
memory: 8252kb

input:

1 4
...#

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 0ms
memory: 8316kb

input:

1 5
####.

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 0ms
memory: 8360kb

input:

1 6
#..###

output:

0

result:

ok 1 number(s): "0"

Test #6:

score: 0
Accepted
time: 0ms
memory: 8584kb

input:

2 5
....#
###.#

output:

3

result:

ok 1 number(s): "3"

Test #7:

score: 0
Accepted
time: 2ms
memory: 8304kb

input:

2 6
...##.
.#.###

output:

4

result:

ok 1 number(s): "4"

Test #8:

score: 0
Accepted
time: 2ms
memory: 8600kb

input:

5 5
##...
##.#.
##.##
##.#.
.##..

output:

7

result:

ok 1 number(s): "7"

Test #9:

score: 0
Accepted
time: 2ms
memory: 8288kb

input:

6 6
...##.
#..#..
......
..#...
#...##
.#....

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: -100
Wrong Answer
time: 0ms
memory: 8580kb

input:

10 10
####.#...#
.#.###....
#....#..#.
.....#.#..
##.#..#.#.
..#..##...
.##.#####.
#######.##
.#.#.##..#
.#.###.##.

output:

23

result:

wrong answer 1st numbers differ - expected: '26', found: '23'