QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#113979#2213. KnightyanranAC ✓353ms102016kbC++141.5kb2023-06-20 11:58:002023-06-20 11:58:04

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:58:04]
  • 评测
  • 测评结果:AC
  • 用时:353ms
  • 内存:102016kb
  • [2023-06-20 11:58:00]
  • 提交

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 * 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] == -1) dfs(v, co ^ 1);
}

int main() {
	memset(col, -1, sizeof(col));
	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;
}
/*
不可能走出奇环,所以是二分图
*/

详细

Test #1:

score: 100
Accepted
time: 25ms
memory: 49248kb

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 0
Accepted
time: 10ms
memory: 33900kb

Test #12:

score: 0
Accepted
time: 38ms
memory: 53020kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

score: 0
Accepted
time: 5ms
memory: 33708kb

Test #18:

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

Test #19:

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

Test #20:

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

Test #21:

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

Test #22:

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

Test #23:

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

Test #24:

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

Test #25:

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

Test #26:

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

Test #27:

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

Test #28:

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

Test #29:

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

Test #30:

score: 0
Accepted
time: 5ms
memory: 36272kb

Test #31:

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

Test #32:

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

Test #33:

score: 0
Accepted
time: 52ms
memory: 49924kb

Test #34:

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

Test #35:

score: 0
Accepted
time: 70ms
memory: 49600kb

Test #36:

score: 0
Accepted
time: 92ms
memory: 51528kb

Test #37:

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

Test #38:

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

Test #39:

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

Test #40:

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

Test #41:

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

Test #42:

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

Test #43:

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

Test #44:

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

Test #45:

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

Test #46:

score: 0
Accepted
time: 10ms
memory: 33812kb

Test #47:

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

Test #48:

score: 0
Accepted
time: 80ms
memory: 47632kb

Test #49:

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

Test #50:

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

Test #51:

score: 0
Accepted
time: 225ms
memory: 67356kb

Test #52:

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

Test #53:

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

Test #54:

score: 0
Accepted
time: 283ms
memory: 87952kb

Test #55:

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

Test #56:

score: 0
Accepted
time: 312ms
memory: 84096kb

Test #57:

score: 0
Accepted
time: 83ms
memory: 51412kb

Test #58:

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

Test #59:

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

Test #60:

score: 0
Accepted
time: 315ms
memory: 88168kb

Test #61:

score: 0
Accepted
time: 59ms
memory: 50712kb

Test #62:

score: 0
Accepted
time: 52ms
memory: 45828kb

Test #63:

score: 0
Accepted
time: 222ms
memory: 68472kb

Test #64:

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

Test #65:

score: 0
Accepted
time: 217ms
memory: 80868kb

Test #66:

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

Test #67:

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

Test #68:

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

Test #69:

score: 0
Accepted
time: 330ms
memory: 91300kb

Test #70:

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

Test #71:

score: 0
Accepted
time: 46ms
memory: 48660kb

Test #72:

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

Test #73:

score: 0
Accepted
time: 37ms
memory: 53756kb

Test #74:

score: 0
Accepted
time: 330ms
memory: 85800kb

Test #75:

score: 0
Accepted
time: 97ms
memory: 54720kb

Test #76:

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

Test #77:

score: 0
Accepted
time: 268ms
memory: 75204kb

Test #78:

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

Test #79:

score: 0
Accepted
time: 45ms
memory: 45024kb

Test #80:

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

Test #81:

score: 0
Accepted
time: 70ms
memory: 55420kb

Test #82:

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

Test #83:

score: 0
Accepted
time: 77ms
memory: 51268kb

Test #84:

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

Test #85:

score: 0
Accepted
time: 18ms
memory: 40228kb

Test #86:

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

Test #87:

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

Test #88:

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

Test #89:

score: 0
Accepted
time: 301ms
memory: 82668kb

Test #90:

score: 0
Accepted
time: 88ms
memory: 52724kb

Test #91:

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

Test #92:

score: 0
Accepted
time: 186ms
memory: 72984kb

Test #93:

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

Test #94:

score: 0
Accepted
time: 320ms
memory: 78428kb

Test #95:

score: 0
Accepted
time: 188ms
memory: 74604kb

Test #96:

score: 0
Accepted
time: 85ms
memory: 56384kb

Test #97:

score: 0
Accepted
time: 286ms
memory: 82452kb

Test #98:

score: 0
Accepted
time: 199ms
memory: 68280kb

Test #99:

score: 0
Accepted
time: 118ms
memory: 66324kb

Test #100:

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

Test #101:

score: 0
Accepted
time: 199ms
memory: 78472kb

Test #102:

score: 0
Accepted
time: 176ms
memory: 78640kb

Test #103:

score: 0
Accepted
time: 309ms
memory: 79844kb

Test #104:

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

Test #105:

score: 0
Accepted
time: 157ms
memory: 63640kb

Test #106:

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

Test #107:

score: 0
Accepted
time: 273ms
memory: 76784kb

Test #108:

score: 0
Accepted
time: 344ms
memory: 87384kb

Test #109:

score: 0
Accepted
time: 192ms
memory: 60636kb

Test #110:

score: 0
Accepted
time: 294ms
memory: 79256kb

Test #111:

score: 0
Accepted
time: 176ms
memory: 60624kb

Test #112:

score: 0
Accepted
time: 172ms
memory: 73516kb

Test #113:

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

Test #114:

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

Test #115:

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

Test #116:

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

Test #117:

score: 0
Accepted
time: 199ms
memory: 81068kb

Test #118:

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

Test #119:

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

Test #120:

score: 0
Accepted
time: 221ms
memory: 68380kb

Test #121:

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

Test #122:

score: 0
Accepted
time: 52ms
memory: 55456kb

Test #123:

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

Test #124:

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

Test #125:

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

Test #126:

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

Test #127:

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

Test #128:

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

Test #129:

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

Test #130:

score: 0
Accepted
time: 162ms
memory: 62924kb

Test #131:

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

Test #132:

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

Test #133:

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

Test #134:

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

Test #135:

score: 0
Accepted
time: 321ms
memory: 87948kb

Test #136:

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

Test #137:

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

Test #138:

score: 0
Accepted
time: 334ms
memory: 92376kb

Test #139:

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

Test #140:

score: 0
Accepted
time: 44ms
memory: 53052kb

Test #141:

score: 0
Accepted
time: 186ms
memory: 70880kb

Test #142:

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

Test #143:

score: 0
Accepted
time: 353ms
memory: 92416kb

Test #144:

score: 0
Accepted
time: 104ms
memory: 53892kb

Test #145:

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

Test #146:

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

Test #147:

score: 0
Accepted
time: 237ms
memory: 81252kb

Test #148:

score: 0
Accepted
time: 272ms
memory: 77688kb

Test #149:

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

Test #150:

score: 0
Accepted
time: 248ms
memory: 77568kb

Test #151:

score: 0
Accepted
time: 349ms
memory: 102016kb

Test #152:

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

Test #153:

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

Test #154:

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

Test #155:

score: 0
Accepted
time: 273ms
memory: 74444kb

Test #156:

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

Test #157:

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

Test #158:

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

Test #159:

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

Test #160:

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

Test #161:

score: 0
Accepted
time: 89ms
memory: 49160kb

Test #162:

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

Test #163:

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

Test #164:

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

Test #165:

score: 0
Accepted
time: 290ms
memory: 82928kb

Test #166:

score: 0
Accepted
time: 279ms
memory: 72168kb