답안 #978386

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978386	2024-05-09T07:44:07 Z	Bodisha	Mecho (IOI09_mecho)	C++17	19 / 100	1000 ms	7716 KB

mecho

#include <bits/stdc++.h>
#define MAX_N 801

using namespace std;

int n, s;
char grid[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
int beed[MAX_N][MAX_N];
int steps[MAX_N][MAX_N];

bool check(int t) {
    vector<pair<int, int>> hives;
    pair<int, int> mecho_pos, home_pos;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            beed[i][j] = n * n;
            visited[i][j] = false;
            steps[i][j] = n * n;
            if(grid[i][j] == 'H') {
                hives.push_back({i, j});
            }
            if(grid[i][j] == 'M') {
                mecho_pos = {i, j};
            }
            if(grid[i][j] == 'D') {
                home_pos = {i, j};
            }
        }
    }
    queue<pair<int, int>> q;
    for(auto iter : hives) {
        visited[iter.first][iter.second] = true;
        beed[iter.first][iter.second] = 0;
        q.push(iter);
    }
    while(!q.empty()) {
        pair<int, int> curr = q.front(); 
        q.pop();
        if(curr.first + 1 < n && !visited[curr.first + 1][curr.second] && (grid[curr.first + 1][curr.second] == 'G' || grid[curr.first + 1][curr.second] == 'M')) {
            visited[curr.first + 1][curr.second] = true;
            beed[curr.first + 1][curr.second] = beed[curr.first][curr.second] + 1;
            q.push({curr.first + 1, curr.second});
        }
        if(curr.first - 1 >= 0 && !visited[curr.first - 1][curr.second] && (grid[curr.first - 1][curr.second] == 'G' || grid[curr.first - 1][curr.second] == 'M')) {
            visited[curr.first - 1][curr.second] = true;
            beed[curr.first - 1][curr.second] = beed[curr.first][curr.second] + 1;
            q.push({curr.first - 1, curr.second});
        }
        if(curr.second + 1 < n && !visited[curr.first][curr.second + 1] && (grid[curr.first][curr.second + 1] == 'G' || grid[curr.first][curr.second + 1] == 'M')) {
            visited[curr.first][curr.second + 1] = true;
            beed[curr.first][curr.second + 1] = beed[curr.first][curr.second] + 1;
            q.push({curr.first, curr.second + 1});
        }
        if(curr.second - 1 >= 0 && !visited[curr.first][curr.second - 1] && (grid[curr.first][curr.second - 1] == 'G' || grid[curr.first][curr.second - 1] == 'M')) {
            visited[curr.first][curr.second - 1] = true;
            beed[curr.first][curr.second - 1] = beed[curr.first][curr.second] + 1;
            q.push({curr.first, curr.second - 1});
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            visited[i][j] = false;
        }
    }
    visited[mecho_pos.first][mecho_pos.second] = true;
    steps[mecho_pos.first][mecho_pos.second] = 0;
    q.push(mecho_pos);
    while(!q.empty()) {
        pair<int, int> curr = q.front(); 
        q.pop();
        if(curr.first + 1 < n && !visited[curr.first + 1][curr.second] && (grid[curr.first + 1][curr.second] == 'G' || grid[curr.first + 1][curr.second] == 'M' || grid[curr.first + 1][curr.second] == 'D')) {
            visited[curr.first + 1][curr.second] = true;
            steps[curr.first + 1][curr.second] = steps[curr.first][curr.second] + 1;
            q.push({curr.first + 1, curr.second});
        }
        if(curr.first - 1 >= 0 && !visited[curr.first - 1][curr.second] && (grid[curr.first - 1][curr.second] == 'G' || grid[curr.first - 1][curr.second] == 'M' || grid[curr.first - 1][curr.second] == 'D')) {
            visited[curr.first - 1][curr.second] = true;
            steps[curr.first - 1][curr.second] = steps[curr.first][curr.second] + 1;
            q.push({curr.first - 1, curr.second});
        }
        if(curr.second + 1 < n && !visited[curr.first][curr.second + 1] && (grid[curr.first][curr.second + 1] == 'G' || grid[curr.first][curr.second + 1] == 'M' || grid[curr.first][curr.second + 1] == 'D')) {
            visited[curr.first][curr.second + 1] = true;
            steps[curr.first][curr.second + 1] = steps[curr.first][curr.second] + 1;
            q.push({curr.first, curr.second + 1});
        }
        if(curr.second - 1 >= 0 && !visited[curr.first][curr.second - 1] && (grid[curr.first][curr.second - 1] == 'G' || grid[curr.first][curr.second - 1] == 'M' || grid[curr.first][curr.second - 1] == 'D')) {
            visited[curr.first][curr.second - 1] = true;
            steps[curr.first][curr.second - 1] = steps[curr.first][curr.second] + 1;
            q.push({curr.first, curr.second - 1});
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            visited[i][j] = false;
        }
    }
    if(t + 1 > beed[mecho_pos.first][mecho_pos.second]) {
        return false;
    }
    queue<pair<pair<int, int>, int>> newq;
    visited[mecho_pos.first][mecho_pos.second] = true;
    newq.push({mecho_pos, 0});
    while(!newq.empty()) {
        pair<pair<int, int>, int> curr = newq.front(); 
        newq.pop();
        int tmp = t + 1 + ((curr.second + 1) / (s + 1));
        if(curr.first.first + 1 < n && tmp <= beed[curr.first.first + 1][curr.first.second] && !visited[curr.first.first + 1][curr.first.second] && (grid[curr.first.first + 1][curr.first.second] == 'G' || grid[curr.first.first + 1][curr.first.second] == 'M' || grid[curr.first.first + 1][curr.first.second] == 'D')) {
            visited[curr.first.first + 1][curr.first.second] = true;
            newq.push({{curr.first.first + 1, curr.first.second}, curr.second + 1});
        }
        if(curr.first.first - 1 >= 0 && tmp <= beed[curr.first.first - 1][curr.first.second] && !visited[curr.first.first - 1][curr.second] && (grid[curr.first.first - 1][curr.first.second] == 'G' || grid[curr.first.first - 1][curr.first.second] == 'M' || grid[curr.first.first - 1][curr.first.second] == 'D')) {
            visited[curr.first.first - 1][curr.first.second] = true;
            newq.push({{curr.first.first - 1, curr.first.second}, curr.second + 1});
        }
        if(curr.first.second + 1 < n && tmp <= beed[curr.first.first][curr.first.second + 1] && !visited[curr.first.first][curr.first.second + 1] && (grid[curr.first.first][curr.first.second + 1] == 'G' || grid[curr.first.first][curr.first.second + 1] == 'M' || grid[curr.first.first][curr.first.second + 1] == 'D')) {
            visited[curr.first.first][curr.first.second + 1] = true;
            newq.push({{curr.first.first, curr.first.second + 1}, curr.second + 1});
        }
        if(curr.first.second - 1 >= 0 && tmp <= beed[curr.first.first][curr.first.second - 1] && !visited[curr.first.first][curr.first.second - 1] && (grid[curr.first.first][curr.first.second - 1] == 'G' || grid[curr.first.first][curr.first.second - 1] == 'M' || grid[curr.first.first][curr.first.second - 1] == 'D')) {
            visited[curr.first.first][curr.first.second - 1] = true;
            newq.push({{curr.first.first, curr.first.second - 1}, curr.second + 1});
        }
    }
    return visited[home_pos.first][home_pos.second];
}

int main() {
    cin >> n >> s;
    for(int i = 0; i < n; i++) {
        string tmp;
        cin >> tmp;
        for(int j = 0; j < n; j++) {
            grid[i][j] = tmp[j];
        }
    }
    int l = 0, r = n * n + 1;
    int ans = -1;
    // true true true ... (true) false false
    while(l <= r) {
        int mid = l + (r - l) / 2;
        if(check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans;
    return 0;
}

Subtask #1

19.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	2396 KB	Output isn't correct
2	Incorrect	1 ms	2396 KB	Output isn't correct
3	Incorrect	1 ms	2504 KB	Output isn't correct
4	Incorrect	1 ms	2392 KB	Output isn't correct
5	Correct	1 ms	2396 KB	Output is correct
6	Incorrect	1 ms	2396 KB	Output isn't correct
7	Execution timed out	1085 ms	7260 KB	Time limit exceeded
8	Incorrect	1 ms	2396 KB	Output isn't correct
9	Correct	1 ms	2396 KB	Output is correct
10	Incorrect	1 ms	2396 KB	Output isn't correct
11	Incorrect	1 ms	2396 KB	Output isn't correct
12	Correct	2 ms	4696 KB	Output is correct
13	Correct	2 ms	2652 KB	Output is correct
14	Incorrect	3 ms	4700 KB	Output isn't correct
15	Incorrect	1 ms	2396 KB	Output isn't correct
16	Correct	1 ms	2396 KB	Output is correct
17	Incorrect	1 ms	2396 KB	Output isn't correct
18	Correct	1 ms	2396 KB	Output is correct
19	Incorrect	1 ms	2492 KB	Output isn't correct
20	Correct	1 ms	2396 KB	Output is correct
21	Incorrect	1 ms	2496 KB	Output isn't correct
22	Correct	1 ms	2652 KB	Output is correct
23	Incorrect	1 ms	2652 KB	Output isn't correct
24	Correct	1 ms	2652 KB	Output is correct
25	Incorrect	2 ms	4700 KB	Output isn't correct
26	Correct	2 ms	4700 KB	Output is correct
27	Incorrect	2 ms	4832 KB	Output isn't correct
28	Correct	2 ms	4696 KB	Output is correct
29	Incorrect	2 ms	4696 KB	Output isn't correct
30	Correct	2 ms	4700 KB	Output is correct
31	Incorrect	2 ms	4700 KB	Output isn't correct
32	Correct	3 ms	4700 KB	Output is correct
33	Incorrect	39 ms	5212 KB	Output isn't correct
34	Correct	30 ms	5208 KB	Output is correct
35	Correct	343 ms	5404 KB	Output is correct
36	Incorrect	56 ms	5212 KB	Output isn't correct
37	Correct	39 ms	5208 KB	Output is correct
38	Correct	357 ms	5684 KB	Output is correct
39	Incorrect	70 ms	5464 KB	Output isn't correct
40	Correct	50 ms	5464 KB	Output is correct
41	Correct	384 ms	5984 KB	Output is correct
42	Incorrect	88 ms	5464 KB	Output isn't correct
43	Correct	60 ms	5672 KB	Output is correct
44	Correct	501 ms	6116 KB	Output is correct
45	Incorrect	110 ms	5724 KB	Output isn't correct
46	Correct	73 ms	5724 KB	Output is correct
47	Correct	560 ms	6252 KB	Output is correct
48	Incorrect	131 ms	5980 KB	Output isn't correct
49	Correct	91 ms	5980 KB	Output is correct
50	Correct	626 ms	6408 KB	Output is correct
51	Incorrect	153 ms	6308 KB	Output isn't correct
52	Correct	106 ms	6236 KB	Output is correct
53	Correct	635 ms	6740 KB	Output is correct
54	Incorrect	182 ms	6508 KB	Output isn't correct
55	Correct	124 ms	6572 KB	Output is correct
56	Correct	596 ms	7044 KB	Output is correct
57	Incorrect	204 ms	6780 KB	Output isn't correct
58	Correct	141 ms	6736 KB	Output is correct
59	Correct	601 ms	7044 KB	Output is correct
60	Incorrect	244 ms	7140 KB	Output isn't correct
61	Correct	161 ms	7000 KB	Output is correct
62	Incorrect	443 ms	7508 KB	Output isn't correct
63	Incorrect	464 ms	7028 KB	Output isn't correct
64	Incorrect	478 ms	7076 KB	Output isn't correct
65	Incorrect	467 ms	7256 KB	Output isn't correct
66	Incorrect	462 ms	7084 KB	Output isn't correct
67	Correct	475 ms	7124 KB	Output is correct
68	Incorrect	426 ms	7004 KB	Output isn't correct
69	Incorrect	441 ms	7252 KB	Output isn't correct
70	Incorrect	443 ms	7160 KB	Output isn't correct
71	Incorrect	441 ms	7168 KB	Output isn't correct
72	Correct	436 ms	7152 KB	Output is correct
73	Correct	600 ms	7680 KB	Output is correct
74	Execution timed out	1065 ms	7556 KB	Time limit exceeded
75	Execution timed out	1025 ms	7448 KB	Time limit exceeded
76	Execution timed out	1016 ms	7484 KB	Time limit exceeded
77	Execution timed out	1069 ms	7624 KB	Time limit exceeded
78	Execution timed out	1077 ms	7640 KB	Time limit exceeded
79	Execution timed out	1049 ms	7584 KB	Time limit exceeded
80	Execution timed out	1098 ms	7468 KB	Time limit exceeded
81	Execution timed out	1059 ms	7532 KB	Time limit exceeded
82	Execution timed out	1022 ms	7616 KB	Time limit exceeded
83	Execution timed out	1066 ms	7352 KB	Time limit exceeded
84	Correct	970 ms	7432 KB	Output is correct
85	Incorrect	875 ms	7508 KB	Output isn't correct
86	Execution timed out	1031 ms	7256 KB	Time limit exceeded
87	Execution timed out	1025 ms	7660 KB	Time limit exceeded
88	Execution timed out	1039 ms	7644 KB	Time limit exceeded
89	Execution timed out	1031 ms	7248 KB	Time limit exceeded
90	Execution timed out	1049 ms	7316 KB	Time limit exceeded
91	Execution timed out	1006 ms	7716 KB	Time limit exceeded
92	Execution timed out	1092 ms	7508 KB	Time limit exceeded