QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#393143#2213. KnightieeAC ✓178ms75724kbC++141.6kb2024-04-18 10:52:232024-04-18 10:52:23

Judging History

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

  • [2024-04-18 10:52:23]
  • 评测
  • 测评结果:AC
  • 用时:178ms
  • 内存:75724kb
  • [2024-04-18 10:52:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m, a, b;
	cin >> n >> m >> a >> b;
	vector<array<int, 2>> dir{{a, b}, {a, -b}, {-a, b}, {-a, -b}, {b, a}, {b, -a}, {-b, a}, {-b, -a}};
	auto id = [&](int x, int y) { return x * m + y; };
	vector<vector<char>> g(n, vector<char>(m));
	int pa = 0, pb = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> g[i][j];
			if (g[i][j] == 'A') pa = id(i, j);
			if (g[i][j] == 'B') pb = id(i, j);
		}
	}
	vector<vector<int>> e(n * m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (g[i][j] != '@') {
				for (auto [x, y] : dir) {
					int ni = i + x, nj = j + y;
					if (ni >= 0 && ni < n && nj >= 0 && nj < m && g[ni][nj] != '@') {
						e[id(i, j)].push_back(id(ni, nj));
					}
				}
			}
		}
	}
	if (e[pa].empty()) {
		cout << "Bob" << "\n";
		return 0;
	}
	int hpa = 0, hpb = 0;
	vector<int> col(n * m, -1);
	for (int i = 0; i < n * m; i++) {
		if (col[i] == -1) {
			static queue<int> q;
			col[i] = 0;
			q.push(i);
			while (!q.empty()) {
				int u = q.front();
				q.pop();
				hpa |= u == pa, hpb |= u == pb;
				for (int v : e[u]) {
					if (col[v] == -1) {
						col[v] = !col[u];
						q.push(v);
					} else assert(col[u] ^ col[v]);
				}
			}
			if (hpa ^ hpb) {
				cout << "Alice" << "\n";
				return 0;
			}
			if (hpa && hpb) {
				if (col[pa] == col[pb]) {
					cout << "Alice" << "\n";
				} else {
					cout << "Bob" << "\n";
				}
				return 0;
			}
		}
	}
	assert(false);
	return 0;
}

Details

Test #1:

score: 100
Accepted
time: 26ms
memory: 29840kb

Test #2:

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

Test #3:

score: 0
Accepted
time: 56ms
memory: 34228kb

Test #4:

score: 0
Accepted
time: 48ms
memory: 22888kb

Test #5:

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

Test #6:

score: 0
Accepted
time: 7ms
memory: 12232kb

Test #7:

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

Test #8:

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

Test #9:

score: 0
Accepted
time: 20ms
memory: 31760kb

Test #10:

score: 0
Accepted
time: 11ms
memory: 19972kb

Test #11:

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

Test #12:

score: 0
Accepted
time: 56ms
memory: 41468kb

Test #13:

score: 0
Accepted
time: 13ms
memory: 8676kb

Test #14:

score: 0
Accepted
time: 16ms
memory: 34452kb

Test #15:

score: 0
Accepted
time: 6ms
memory: 6760kb

Test #16:

score: 0
Accepted
time: 8ms
memory: 16728kb

Test #17:

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

Test #18:

score: 0
Accepted
time: 9ms
memory: 9420kb

Test #19:

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

Test #20:

score: 0
Accepted
time: 21ms
memory: 21872kb

Test #21:

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

Test #22:

score: 0
Accepted
time: 6ms
memory: 9228kb

Test #23:

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

Test #24:

score: 0
Accepted
time: 8ms
memory: 14224kb

Test #25:

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

Test #26:

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

Test #27:

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

Test #28:

score: 0
Accepted
time: 58ms
memory: 27812kb

Test #29:

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

Test #30:

score: 0
Accepted
time: 12ms
memory: 20692kb

Test #31:

score: 0
Accepted
time: 8ms
memory: 11772kb

Test #32:

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

Test #33:

score: 0
Accepted
time: 51ms
memory: 31332kb

Test #34:

score: 0
Accepted
time: 8ms
memory: 8808kb

Test #35:

score: 0
Accepted
time: 39ms
memory: 26784kb

Test #36:

score: 0
Accepted
time: 69ms
memory: 43088kb

Test #37:

score: 0
Accepted
time: 8ms
memory: 9944kb

Test #38:

score: 0
Accepted
time: 14ms
memory: 11844kb

Test #39:

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

Test #40:

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

Test #41:

score: 0
Accepted
time: 11ms
memory: 17860kb

Test #42:

score: 0
Accepted
time: 7ms
memory: 12428kb

Test #43:

score: 0
Accepted
time: 13ms
memory: 24440kb

Test #44:

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

Test #45:

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

Test #46:

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

Test #47:

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

Test #48:

score: 0
Accepted
time: 60ms
memory: 34352kb

Test #49:

score: 0
Accepted
time: 19ms
memory: 30660kb

Test #50:

score: 0
Accepted
time: 14ms
memory: 14572kb

Test #51:

score: 0
Accepted
time: 125ms
memory: 55516kb

Test #52:

score: 0
Accepted
time: 129ms
memory: 59404kb

Test #53:

score: 0
Accepted
time: 32ms
memory: 36728kb

Test #54:

score: 0
Accepted
time: 147ms
memory: 72208kb

Test #55:

score: 0
Accepted
time: 78ms
memory: 47432kb

Test #56:

score: 0
Accepted
time: 148ms
memory: 66816kb

Test #57:

score: 0
Accepted
time: 86ms
memory: 47004kb

Test #58:

score: 0
Accepted
time: 24ms
memory: 30844kb

Test #59:

score: 0
Accepted
time: 31ms
memory: 36452kb

Test #60:

score: 0
Accepted
time: 158ms
memory: 68304kb

Test #61:

score: 0
Accepted
time: 62ms
memory: 46420kb

Test #62:

score: 0
Accepted
time: 50ms
memory: 41152kb

Test #63:

score: 0
Accepted
time: 132ms
memory: 57188kb

Test #64:

score: 0
Accepted
time: 43ms
memory: 36428kb

Test #65:

score: 0
Accepted
time: 125ms
memory: 73956kb

Test #66:

score: 0
Accepted
time: 31ms
memory: 36388kb

Test #67:

score: 0
Accepted
time: 120ms
memory: 51108kb

Test #68:

score: 0
Accepted
time: 41ms
memory: 35260kb

Test #69:

score: 0
Accepted
time: 178ms
memory: 69512kb

Test #70:

score: 0
Accepted
time: 69ms
memory: 41880kb

Test #71:

score: 0
Accepted
time: 72ms
memory: 44296kb

Test #72:

score: 0
Accepted
time: 27ms
memory: 35324kb

Test #73:

score: 0
Accepted
time: 39ms
memory: 45712kb

Test #74:

score: 0
Accepted
time: 152ms
memory: 66500kb

Test #75:

score: 0
Accepted
time: 94ms
memory: 50528kb

Test #76:

score: 0
Accepted
time: 103ms
memory: 52540kb

Test #77:

score: 0
Accepted
time: 134ms
memory: 60564kb

Test #78:

score: 0
Accepted
time: 26ms
memory: 35148kb

Test #79:

score: 0
Accepted
time: 48ms
memory: 36776kb

Test #80:

score: 0
Accepted
time: 95ms
memory: 52180kb

Test #81:

score: 0
Accepted
time: 78ms
memory: 50984kb

Test #82:

score: 0
Accepted
time: 82ms
memory: 48052kb

Test #83:

score: 0
Accepted
time: 73ms
memory: 43052kb

Test #84:

score: 0
Accepted
time: 54ms
memory: 40136kb

Test #85:

score: 0
Accepted
time: 23ms
memory: 35848kb

Test #86:

score: 0
Accepted
time: 21ms
memory: 35876kb

Test #87:

score: 0
Accepted
time: 34ms
memory: 40152kb

Test #88:

score: 0
Accepted
time: 40ms
memory: 36056kb

Test #89:

score: 0
Accepted
time: 140ms
memory: 65680kb

Test #90:

score: 0
Accepted
time: 94ms
memory: 48320kb

Test #91:

score: 0
Accepted
time: 21ms
memory: 35416kb

Test #92:

score: 0
Accepted
time: 122ms
memory: 68400kb

Test #93:

score: 0
Accepted
time: 35ms
memory: 34276kb

Test #94:

score: 0
Accepted
time: 155ms
memory: 62968kb

Test #95:

score: 0
Accepted
time: 121ms
memory: 69404kb

Test #96:

score: 0
Accepted
time: 69ms
memory: 51952kb

Test #97:

score: 0
Accepted
time: 164ms
memory: 63760kb

Test #98:

score: 0
Accepted
time: 129ms
memory: 60344kb

Test #99:

score: 0
Accepted
time: 86ms
memory: 61540kb

Test #100:

score: 0
Accepted
time: 107ms
memory: 63772kb

Test #101:

score: 0
Accepted
time: 138ms
memory: 73584kb

Test #102:

score: 0
Accepted
time: 112ms
memory: 73012kb

Test #103:

score: 0
Accepted
time: 134ms
memory: 63436kb

Test #104:

score: 0
Accepted
time: 66ms
memory: 41352kb

Test #105:

score: 0
Accepted
time: 136ms
memory: 59148kb

Test #106:

score: 0
Accepted
time: 60ms
memory: 50636kb

Test #107:

score: 0
Accepted
time: 124ms
memory: 61716kb

Test #108:

score: 0
Accepted
time: 164ms
memory: 67952kb

Test #109:

score: 0
Accepted
time: 123ms
memory: 51580kb

Test #110:

score: 0
Accepted
time: 150ms
memory: 66080kb

Test #111:

score: 0
Accepted
time: 116ms
memory: 53980kb

Test #112:

score: 0
Accepted
time: 105ms
memory: 67544kb

Test #113:

score: 0
Accepted
time: 25ms
memory: 31616kb

Test #114:

score: 0
Accepted
time: 25ms
memory: 30968kb

Test #115:

score: 0
Accepted
time: 40ms
memory: 36892kb

Test #116:

score: 0
Accepted
time: 136ms
memory: 68660kb

Test #117:

score: 0
Accepted
time: 124ms
memory: 74476kb

Test #118:

score: 0
Accepted
time: 23ms
memory: 33728kb

Test #119:

score: 0
Accepted
time: 14ms
memory: 29592kb

Test #120:

score: 0
Accepted
time: 131ms
memory: 54260kb

Test #121:

score: 0
Accepted
time: 40ms
memory: 37524kb

Test #122:

score: 0
Accepted
time: 48ms
memory: 47084kb

Test #123:

score: 0
Accepted
time: 28ms
memory: 32812kb

Test #124:

score: 0
Accepted
time: 40ms
memory: 38780kb

Test #125:

score: 0
Accepted
time: 94ms
memory: 46440kb

Test #126:

score: 0
Accepted
time: 24ms
memory: 35720kb

Test #127:

score: 0
Accepted
time: 15ms
memory: 29496kb

Test #128:

score: 0
Accepted
time: 47ms
memory: 56124kb

Test #129:

score: 0
Accepted
time: 34ms
memory: 39168kb

Test #130:

score: 0
Accepted
time: 116ms
memory: 58256kb

Test #131:

score: 0
Accepted
time: 30ms
memory: 35388kb

Test #132:

score: 0
Accepted
time: 113ms
memory: 49324kb

Test #133:

score: 0
Accepted
time: 23ms
memory: 31968kb

Test #134:

score: 0
Accepted
time: 61ms
memory: 44624kb

Test #135:

score: 0
Accepted
time: 170ms
memory: 67004kb

Test #136:

score: 0
Accepted
time: 25ms
memory: 30396kb

Test #137:

score: 0
Accepted
time: 28ms
memory: 37744kb

Test #138:

score: 0
Accepted
time: 159ms
memory: 68888kb

Test #139:

score: 0
Accepted
time: 33ms
memory: 34684kb

Test #140:

score: 0
Accepted
time: 57ms
memory: 48532kb

Test #141:

score: 0
Accepted
time: 120ms
memory: 64708kb

Test #142:

score: 0
Accepted
time: 40ms
memory: 35960kb

Test #143:

score: 0
Accepted
time: 171ms
memory: 70160kb

Test #144:

score: 0
Accepted
time: 98ms
memory: 49308kb

Test #145:

score: 0
Accepted
time: 109ms
memory: 60848kb

Test #146:

score: 0
Accepted
time: 72ms
memory: 42012kb

Test #147:

score: 0
Accepted
time: 141ms
memory: 74392kb

Test #148:

score: 0
Accepted
time: 153ms
memory: 63372kb

Test #149:

score: 0
Accepted
time: 86ms
memory: 57984kb

Test #150:

score: 0
Accepted
time: 137ms
memory: 63504kb

Test #151:

score: 0
Accepted
time: 168ms
memory: 75724kb

Test #152:

score: 0
Accepted
time: 29ms
memory: 35620kb

Test #153:

score: 0
Accepted
time: 22ms
memory: 32204kb

Test #154:

score: 0
Accepted
time: 43ms
memory: 36868kb

Test #155:

score: 0
Accepted
time: 159ms
memory: 58100kb

Test #156:

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

Test #157:

score: 0
Accepted
time: 35ms
memory: 50640kb

Test #158:

score: 0
Accepted
time: 76ms
memory: 48304kb

Test #159:

score: 0
Accepted
time: 16ms
memory: 30268kb

Test #160:

score: 0
Accepted
time: 31ms
memory: 36124kb

Test #161:

score: 0
Accepted
time: 69ms
memory: 41936kb

Test #162:

score: 0
Accepted
time: 30ms
memory: 37944kb

Test #163:

score: 0
Accepted
time: 21ms
memory: 28680kb

Test #164:

score: 0
Accepted
time: 99ms
memory: 52112kb

Test #165:

score: 0
Accepted
time: 178ms
memory: 68664kb

Test #166:

score: 0
Accepted
time: 142ms
memory: 57440kb