QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#17948#2213. Knightnamelessgugugu#AC ✓156ms14476kbC++141.7kb2022-01-15 14:05:232022-05-04 16:30:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-04 16:30:22]
  • 评测
  • 测评结果:AC
  • 用时:156ms
  • 内存:14476kb
  • [2022-01-15 14:05:23]
  • 提交

answer

#include <algorithm>
#include <cstdio>
#include <cstring>
const int N = 1005;
int n, m, r, c, pa, pb;
char s[N][N];
int fa[N * N], val[N * N], siz[N * N];
inline int find(int x)
{
    if (fa[x] == x)
        return x;
    int res = find(fa[x]);
    val[x] ^= val[fa[x]];
    return fa[x] = res;
}
inline void merge(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx == fy)
        return;
    fa[fx] = fy, siz[fy] += siz[fx], val[fx] = !(val[x] ^ val[y]);
    return;
}
int main(void)
{
    scanf("%d%d%d%d", &n, &m, &r, &c);
    for (int i = 1; i <= n; ++i)
        scanf("%s", s[i] + 1);
    int dx[] = {r, r, -r, -r, c, c, -c, -c};
    int dy[] = {c, -c, c, -c, r, -r, r, -r};
    for (int i = 1; i <= n * m; ++i)
        fa[i] = i, val[i] = 0, siz[i] = 1;
    for (int x = 1; x <= n; ++x)
        for (int y = 1; y <= m; ++y)
            if (s[x][y] != '@')
            {
                for (int k = 0; k < 8; ++k)
                {
                    int nx = x + dx[k], ny = y + dy[k];
                    if (nx < 1 || ny < 1 || nx > n || ny > m || s[nx][ny] == '@')
                        continue;
                    merge((x - 1) * m + y, (nx - 1) * m + ny);
                }
            }
    for (int x = 1; x <= n; ++x)
        for (int y = 1; y <= m; ++y)
            if (s[x][y] == 'A')
            {
                pa = (x - 1) * m + y;
            }
            else if (s[x][y] == 'B')
            {
                pb = (x - 1) * m + y;
            }
    if (siz[find(pa)] == 1)
        return puts("Bob"), 0;
    if (find(pa) != find(pb))
        return puts("Alice"), 0;
    find(pa), find(pb);
    puts(val[pa] == val[pb] ? "Alice" : "Bob");
    return 0;
}

Details

Test #1:

score: 100
Accepted
time: 17ms
memory: 14224kb

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 0
Accepted
time: 17ms
memory: 13916kb

Test #10:

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

Test #11:

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

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

score: 0
Accepted
time: 17ms
memory: 14276kb

Test #17:

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

Test #18:

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

Test #19:

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

Test #20:

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

Test #21:

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

Test #22:

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

Test #23:

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

Test #24:

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

Test #25:

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

Test #26:

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

Test #27:

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

Test #28:

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

Test #29:

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

Test #30:

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

Test #31:

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

Test #32:

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

Test #33:

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

Test #34:

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

Test #35:

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

Test #36:

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

Test #37:

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

Test #38:

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

Test #39:

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

Test #40:

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

Test #41:

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

Test #42:

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

Test #43:

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

Test #44:

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

Test #45:

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

Test #46:

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

Test #47:

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

Test #48:

score: 0
Accepted
time: 65ms
memory: 14412kb

Test #49:

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

Test #50:

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

Test #51:

score: 0
Accepted
time: 114ms
memory: 14476kb

Test #52:

score: 0
Accepted
time: 135ms
memory: 14404kb

Test #53:

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

Test #54:

score: 0
Accepted
time: 151ms
memory: 14404kb

Test #55:

score: 0
Accepted
time: 84ms
memory: 14368kb

Test #56:

score: 0
Accepted
time: 108ms
memory: 14288kb

Test #57:

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

Test #58:

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

Test #59:

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

Test #60:

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

Test #61:

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

Test #62:

score: 0
Accepted
time: 49ms
memory: 14292kb

Test #63:

score: 0
Accepted
time: 111ms
memory: 14388kb

Test #64:

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

Test #65:

score: 0
Accepted
time: 151ms
memory: 14368kb

Test #66:

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

Test #67:

score: 0
Accepted
time: 87ms
memory: 14368kb

Test #68:

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

Test #69:

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

Test #70:

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

Test #71:

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

Test #72:

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

Test #73:

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

Test #74:

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

Test #75:

score: 0
Accepted
time: 74ms
memory: 14388kb

Test #76:

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

Test #77:

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

Test #78:

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

Test #79:

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

Test #80:

score: 0
Accepted
time: 65ms
memory: 14324kb

Test #81:

score: 0
Accepted
time: 55ms
memory: 14404kb

Test #82:

score: 0
Accepted
time: 79ms
memory: 14404kb

Test #83:

score: 0
Accepted
time: 64ms
memory: 14288kb

Test #84:

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

Test #85:

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

Test #86:

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

Test #87:

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

Test #88:

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

Test #89:

score: 0
Accepted
time: 111ms
memory: 14396kb

Test #90:

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

Test #91:

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

Test #92:

score: 0
Accepted
time: 154ms
memory: 14396kb

Test #93:

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

Test #94:

score: 0
Accepted
time: 130ms
memory: 14420kb

Test #95:

score: 0
Accepted
time: 126ms
memory: 14320kb

Test #96:

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

Test #97:

score: 0
Accepted
time: 146ms
memory: 14420kb

Test #98:

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

Test #99:

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

Test #100:

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

Test #101:

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

Test #102:

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

Test #103:

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

Test #104:

score: 0
Accepted
time: 49ms
memory: 14404kb

Test #105:

score: 0
Accepted
time: 119ms
memory: 14396kb

Test #106:

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

Test #107:

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

Test #108:

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

Test #109:

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

Test #110:

score: 0
Accepted
time: 144ms
memory: 14420kb

Test #111:

score: 0
Accepted
time: 102ms
memory: 14416kb

Test #112:

score: 0
Accepted
time: 115ms
memory: 14324kb

Test #113:

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

Test #114:

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

Test #115:

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

Test #116:

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

Test #117:

score: 0
Accepted
time: 146ms
memory: 14444kb

Test #118:

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

Test #119:

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

Test #120:

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

Test #121:

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

Test #122:

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

Test #123:

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

Test #124:

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

Test #125:

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

Test #126:

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

Test #127:

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

Test #128:

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

Test #129:

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

Test #130:

score: 0
Accepted
time: 126ms
memory: 14476kb

Test #131:

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

Test #132:

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

Test #133:

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

Test #134:

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

Test #135:

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

Test #136:

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

Test #137:

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

Test #138:

score: 0
Accepted
time: 133ms
memory: 14372kb

Test #139:

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

Test #140:

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

Test #141:

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

Test #142:

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

Test #143:

score: 0
Accepted
time: 139ms
memory: 14440kb

Test #144:

score: 0
Accepted
time: 93ms
memory: 14444kb

Test #145:

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

Test #146:

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

Test #147:

score: 0
Accepted
time: 151ms
memory: 14400kb

Test #148:

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

Test #149:

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

Test #150:

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

Test #151:

score: 0
Accepted
time: 156ms
memory: 14388kb

Test #152:

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

Test #153:

score: 0
Accepted
time: 17ms
memory: 14392kb

Test #154:

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

Test #155:

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

Test #156:

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

Test #157:

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

Test #158:

score: 0
Accepted
time: 42ms
memory: 14372kb

Test #159:

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

Test #160:

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

Test #161:

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

Test #162:

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

Test #163:

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

Test #164:

score: 0
Accepted
time: 93ms
memory: 14412kb

Test #165:

score: 0
Accepted
time: 145ms
memory: 14432kb

Test #166:

score: 0
Accepted
time: 127ms
memory: 14384kb