QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#52809#2213. KnightFamiglistmo#AC ✓397ms97236kbC++141.5kb2022-10-04 15:13:322022-10-04 15:13:38

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-04 15:13:38]
  • 评测
  • 测评结果:AC
  • 用时:397ms
  • 内存:97236kb
  • [2022-10-04 15:13:32]
  • 提交

answer

#include <bits/stdc++.h>
#define id(x, y) ((x - 1) * m + y)
using namespace std;
const int N = 1005;

int col[N * N], bl[N * N];
vector<int> Edge[N * N];
int n, m, r, c, xa, ya, xb, yb, cnt;
char s[N][N];

void dfs(int u, int c) {
    col[u] = c, bl[u] = cnt;
    for(auto v : Edge[u]) 
        if(!col[v]) dfs(v, 3 - c);
}

signed main() {
    scanf("%d%d%d%d", &n, &m, &r, &c);
    if(!r && !c) return puts("Bob"), 0;
    int dx[8] = {r, r, -r, -r, c, c, -c, -c};
    int dy[8] = {c, -c, c, -c, r, -r, r, -r};

    for(int i = 1; i <= n; ++ i) {
        scanf("%s", s[i] + 1);
        for(int j = 1; j <= m; ++ j)
            if(s[i][j] == 'A') xa = i, ya = j;
            else if(s[i][j] == 'B') xb = i, yb = j;
    }
    
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j) if(s[i][j] != '@')
            for(int k = 0; k < 8; ++ k) {
                int x = i + dx[k], y = j + dy[k];
                if(x < 1 || x > n || y < 1 || y > m || s[x][y] == '@') continue;
                Edge[id(i, j)].push_back(id(x, y));
            }
    for(int i = 1; i <= n * n; ++ i) if(!col[i]) ++ cnt, dfs(i, 1);

    if(!Edge[id(xa, ya)].size()) return puts("Bob"), 0;
    if(Edge[id(xa, ya)].size() == 1 && Edge[id(xa, ya)].front() == id(xb, yb))
        return puts("Bob"), 0;
    if(bl[id(xa, ya)] ^ bl[id(xb, yb)]) return puts("Alice"), 0;
    if(col[id(xa, ya)] ^ col[id(xb, yb)]) return puts("Bob"), 0;
    puts("Alice");
    return 0;
}

Details

Test #1:

score: 100
Accepted
time: 58ms
memory: 45964kb

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

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

Test #20:

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

Test #21:

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

Test #22:

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

Test #23:

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

Test #24:

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

Test #25:

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

Test #26:

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

Test #27:

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

Test #28:

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

Test #29:

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

Test #30:

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

Test #31:

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

Test #32:

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

Test #33:

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

Test #34:

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

Test #35:

score: 0
Accepted
time: 101ms
memory: 45784kb

Test #36:

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

Test #37:

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

Test #38:

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

Test #39:

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

Test #40:

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

Test #41:

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

Test #42:

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

Test #43:

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

Test #44:

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

Test #45:

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

Test #46:

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

Test #47:

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

Test #48:

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

Test #49:

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

Test #50:

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

Test #51:

score: 0
Accepted
time: 229ms
memory: 64868kb

Test #52:

score: 0
Accepted
time: 260ms
memory: 66428kb

Test #53:

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

Test #54:

score: 0
Accepted
time: 329ms
memory: 84252kb

Test #55:

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

Test #56:

score: 0
Accepted
time: 375ms
memory: 82104kb

Test #57:

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

Test #58:

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

Test #59:

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

Test #60:

score: 0
Accepted
time: 374ms
memory: 83884kb

Test #61:

score: 0
Accepted
time: 149ms
memory: 51008kb

Test #62:

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

Test #63:

score: 0
Accepted
time: 280ms
memory: 67104kb

Test #64:

score: 0
Accepted
time: 75ms
memory: 41208kb

Test #65:

score: 0
Accepted
time: 322ms
memory: 79492kb

Test #66:

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

Test #67:

score: 0
Accepted
time: 181ms
memory: 56432kb

Test #68:

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

Test #69:

score: 0
Accepted
time: 397ms
memory: 88144kb

Test #70:

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

Test #71:

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

Test #72:

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

Test #73:

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

Test #74:

score: 0
Accepted
time: 355ms
memory: 82116kb

Test #75:

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

Test #76:

score: 0
Accepted
time: 175ms
memory: 57140kb

Test #77:

score: 0
Accepted
time: 285ms
memory: 72160kb

Test #78:

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

Test #79:

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

Test #80:

score: 0
Accepted
time: 185ms
memory: 57476kb

Test #81:

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

Test #82:

score: 0
Accepted
time: 163ms
memory: 52856kb

Test #83:

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

Test #84:

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

Test #85:

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

Test #86:

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

Test #87:

score: 0
Accepted
time: 53ms
memory: 44724kb

Test #88:

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

Test #89:

score: 0
Accepted
time: 362ms
memory: 81120kb

Test #90:

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

Test #91:

score: 0
Accepted
time: 36ms
memory: 39920kb

Test #92:

score: 0
Accepted
time: 324ms
memory: 76352kb

Test #93:

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

Test #94:

score: 0
Accepted
time: 302ms
memory: 76324kb

Test #95:

score: 0
Accepted
time: 231ms
memory: 74076kb

Test #96:

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

Test #97:

score: 0
Accepted
time: 295ms
memory: 79900kb

Test #98:

score: 0
Accepted
time: 259ms
memory: 69432kb

Test #99:

score: 0
Accepted
time: 265ms
memory: 66912kb

Test #100:

score: 0
Accepted
time: 276ms
memory: 68708kb

Test #101:

score: 0
Accepted
time: 318ms
memory: 80100kb

Test #102:

score: 0
Accepted
time: 249ms
memory: 77780kb

Test #103:

score: 0
Accepted
time: 343ms
memory: 76464kb

Test #104:

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

Test #105:

score: 0
Accepted
time: 251ms
memory: 64192kb

Test #106:

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

Test #107:

score: 0
Accepted
time: 289ms
memory: 72720kb

Test #108:

score: 0
Accepted
time: 375ms
memory: 83328kb

Test #109:

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

Test #110:

score: 0
Accepted
time: 352ms
memory: 76200kb

Test #111:

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

Test #112:

score: 0
Accepted
time: 288ms
memory: 73416kb

Test #113:

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

Test #114:

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

Test #115:

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

Test #116:

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

Test #117:

score: 0
Accepted
time: 374ms
memory: 81032kb

Test #118:

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

Test #119:

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

Test #120:

score: 0
Accepted
time: 226ms
memory: 66452kb

Test #121:

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

Test #122:

score: 0
Accepted
time: 175ms
memory: 57040kb

Test #123:

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

Test #124:

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

Test #125:

score: 0
Accepted
time: 167ms
memory: 51420kb

Test #126:

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

Test #127:

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

Test #128:

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

Test #129:

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

Test #130:

score: 0
Accepted
time: 265ms
memory: 63576kb

Test #131:

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

Test #132:

score: 0
Accepted
time: 220ms
memory: 59880kb

Test #133:

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

Test #134:

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

Test #135:

score: 0
Accepted
time: 346ms
memory: 84104kb

Test #136:

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

Test #137:

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

Test #138:

score: 0
Accepted
time: 346ms
memory: 86308kb

Test #139:

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

Test #140:

score: 0
Accepted
time: 101ms
memory: 53252kb

Test #141:

score: 0
Accepted
time: 296ms
memory: 72080kb

Test #142:

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

Test #143:

score: 0
Accepted
time: 366ms
memory: 88276kb

Test #144:

score: 0
Accepted
time: 184ms
memory: 54664kb

Test #145:

score: 0
Accepted
time: 271ms
memory: 69648kb

Test #146:

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

Test #147:

score: 0
Accepted
time: 342ms
memory: 83148kb

Test #148:

score: 0
Accepted
time: 299ms
memory: 73780kb

Test #149:

score: 0
Accepted
time: 243ms
memory: 63232kb

Test #150:

score: 0
Accepted
time: 317ms
memory: 75796kb

Test #151:

score: 0
Accepted
time: 323ms
memory: 97236kb

Test #152:

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

Test #153:

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

Test #154:

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

Test #155:

score: 0
Accepted
time: 288ms
memory: 72144kb

Test #156:

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

Test #157:

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

Test #158:

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

Test #159:

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

Test #160:

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

Test #161:

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

Test #162:

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

Test #163:

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

Test #164:

score: 0
Accepted
time: 216ms
memory: 58852kb

Test #165:

score: 0
Accepted
time: 355ms
memory: 78980kb

Test #166:

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