QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113957#2213. KnightyanranWA 63ms48596kbC++141.5kb2023-06-20 11:10:412023-06-20 11:10:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-20 11:10:42]
  • 评测
  • 测评结果:WA
  • 用时:63ms
  • 内存:48596kb
  • [2023-06-20 11:10:41]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int read() {
    int x = 0; char ch = getchar();
    while (ch < '0') ch = getchar();
    while (ch >= '0') x = x * 10 + ch - 48, ch = getchar();
    return x;
}

const int N = 1003;
int n, m, r, c, A, B, fa[N * N], col[N];
char s[N][N];
vector<int> e[N * N];

inline int id(int x, int y) {
	return (x - 1) * m + y;
}
inline int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void link(int a, int x, int y) {
	if (x > n || y > m || y < 1 || s[x][y] == '@') return;
	int b = id(x, y);
	e[a].push_back(b), e[b].push_back(a);
	fa[find(a)] = find(b);
}

void dfs(int u, int co) {
	col[u] = co;
	for (int v : e[u]) if (!col[v]) dfs(v, co ^ 1);
}

int main() {
	n = read(), m = read(), r = read(), c = read();
	for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
	if (!r && !c) return puts("Bob"), 0;
	for (int i = 1; i <= n * m; i++) fa[i] = i;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (s[i][j] == '@') continue;
			if (s[i][j] == 'A') A = id(i, j);
			if (s[i][j] == 'B') B = id(i, j);
			int u = id(i, j);
			link(u, i + r, j + c);
			link(u, i + r, j - c);
			link(u, i + c, j + r);
			link(u, i + c, j - r);
		}
	}
	if (e[A].size() == 0 || (e[A].size() == 1 && e[A][0] == B)) {
		puts("Bob"); return 0;
	}
	if (find(A) != find(B)) {
		puts("Alice"); return 0;
	}
	dfs(A, 0);
	puts(col[A] == col[B] ? "Alice" :"Bob");
	return 0;
}
/*
不可能走出奇环,所以是二分图
*/

Details

Test #1:

score: 100
Accepted
time: 34ms
memory: 43832kb

Test #2:

score: 0
Accepted
time: 3ms
memory: 29044kb

Test #3:

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

Test #4:

score: -100
Wrong Answer
time: 47ms
memory: 37520kb