답안 #978402

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978402	2024-05-09T07:55:14 Z	Bodisha	Mecho (IOI09_mecho)	C++17	0 / 100	1000 ms	8052 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) {
    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] == 'M') {
                mecho_pos = {i, j};
            }
            if(grid[i][j] == 'D') {
                home_pos = {i, j};
            }
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            visited[i][j] = false;
        }
    }
    queue<pair<int, int>> q;
    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 + 1][home_pos.second] || visited[home_pos.first - 1][home_pos.second] || visited[home_pos.first - 1][home_pos.second] || visited[home_pos.first][home_pos.second + 1] || visited[home_pos.first][home_pos.second - 1];
}

int main() {
    vector<pair<int, int>> hives;
    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];
            if(grid[i][j] == 'H') {
                hives.push_back({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});
        }
    }
    int l = 0, r = n * n;
    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

0.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	2396 KB	Output isn't correct
2	Incorrect	1 ms	2396 KB	Output isn't correct
3	Incorrect	1 ms	2392 KB	Output isn't correct
4	Incorrect	1 ms	2396 KB	Output isn't correct
5	Incorrect	0 ms	2396 KB	Output isn't correct
6	Incorrect	1 ms	2396 KB	Output isn't correct
7	Execution timed out	1097 ms	7500 KB	Time limit exceeded
8	Incorrect	1 ms	2392 KB	Output isn't correct
9	Incorrect	1 ms	2644 KB	Output isn't correct
10	Incorrect	1 ms	2396 KB	Output isn't correct
11	Incorrect	1 ms	2396 KB	Output isn't correct
12	Incorrect	1 ms	4700 KB	Output isn't correct
13	Incorrect	3 ms	2652 KB	Output isn't correct
14	Incorrect	7 ms	4700 KB	Output isn't correct
15	Incorrect	1 ms	2396 KB	Output isn't correct
16	Incorrect	1 ms	2396 KB	Output isn't correct
17	Incorrect	1 ms	2396 KB	Output isn't correct
18	Incorrect	1 ms	2396 KB	Output isn't correct
19	Incorrect	1 ms	2396 KB	Output isn't correct
20	Incorrect	1 ms	2396 KB	Output isn't correct
21	Incorrect	2 ms	2652 KB	Output isn't correct
22	Incorrect	1 ms	2652 KB	Output isn't correct
23	Incorrect	1 ms	2652 KB	Output isn't correct
24	Incorrect	1 ms	2652 KB	Output isn't correct
25	Incorrect	1 ms	4696 KB	Output isn't correct
26	Incorrect	1 ms	4700 KB	Output isn't correct
27	Incorrect	2 ms	4700 KB	Output isn't correct
28	Incorrect	2 ms	4700 KB	Output isn't correct
29	Incorrect	2 ms	4700 KB	Output isn't correct
30	Incorrect	2 ms	4696 KB	Output isn't correct
31	Incorrect	2 ms	4700 KB	Output isn't correct
32	Incorrect	2 ms	4700 KB	Output isn't correct
33	Incorrect	26 ms	5268 KB	Output isn't correct
34	Incorrect	18 ms	5212 KB	Output isn't correct
35	Incorrect	791 ms	5752 KB	Output isn't correct
36	Incorrect	34 ms	5208 KB	Output isn't correct
37	Incorrect	22 ms	5212 KB	Output isn't correct
38	Incorrect	736 ms	5588 KB	Output isn't correct
39	Incorrect	43 ms	5212 KB	Output isn't correct
40	Incorrect	28 ms	5212 KB	Output isn't correct
41	Incorrect	736 ms	5464 KB	Output isn't correct
42	Incorrect	54 ms	5468 KB	Output isn't correct
43	Incorrect	34 ms	5484 KB	Output isn't correct
44	Incorrect	815 ms	5708 KB	Output isn't correct
45	Incorrect	66 ms	5468 KB	Output isn't correct
46	Incorrect	41 ms	5468 KB	Output isn't correct
47	Execution timed out	1026 ms	6036 KB	Time limit exceeded
48	Incorrect	78 ms	5760 KB	Output isn't correct
49	Incorrect	52 ms	5968 KB	Output isn't correct
50	Execution timed out	1038 ms	6168 KB	Time limit exceeded
51	Incorrect	92 ms	5996 KB	Output isn't correct
52	Incorrect	62 ms	5980 KB	Output isn't correct
53	Execution timed out	1075 ms	6320 KB	Time limit exceeded
54	Incorrect	107 ms	6232 KB	Output isn't correct
55	Incorrect	69 ms	6236 KB	Output isn't correct
56	Execution timed out	1010 ms	6716 KB	Time limit exceeded
57	Incorrect	127 ms	6236 KB	Output isn't correct
58	Incorrect	85 ms	6236 KB	Output isn't correct
59	Execution timed out	1090 ms	6996 KB	Time limit exceeded
60	Incorrect	144 ms	6692 KB	Output isn't correct
61	Incorrect	89 ms	6688 KB	Output isn't correct
62	Execution timed out	1062 ms	7300 KB	Time limit exceeded
63	Incorrect	361 ms	6700 KB	Output isn't correct
64	Incorrect	346 ms	6704 KB	Output isn't correct
65	Incorrect	358 ms	6700 KB	Output isn't correct
66	Incorrect	349 ms	6704 KB	Output isn't correct
67	Correct	359 ms	6704 KB	Output is correct
68	Incorrect	326 ms	6748 KB	Output isn't correct
69	Incorrect	332 ms	6728 KB	Output isn't correct
70	Incorrect	330 ms	6748 KB	Output isn't correct
71	Incorrect	333 ms	6744 KB	Output isn't correct
72	Incorrect	268 ms	6748 KB	Output isn't correct
73	Execution timed out	1012 ms	7668 KB	Time limit exceeded
74	Execution timed out	1038 ms	7768 KB	Time limit exceeded
75	Execution timed out	1061 ms	7500 KB	Time limit exceeded
76	Execution timed out	1076 ms	7748 KB	Time limit exceeded
77	Execution timed out	1014 ms	7704 KB	Time limit exceeded
78	Execution timed out	1069 ms	8020 KB	Time limit exceeded
79	Execution timed out	1049 ms	7884 KB	Time limit exceeded
80	Execution timed out	1056 ms	8052 KB	Time limit exceeded
81	Execution timed out	1058 ms	7908 KB	Time limit exceeded
82	Execution timed out	1022 ms	8008 KB	Time limit exceeded
83	Execution timed out	1043 ms	7252 KB	Time limit exceeded
84	Execution timed out	1065 ms	7424 KB	Time limit exceeded
85	Execution timed out	1063 ms	7196 KB	Time limit exceeded
86	Execution timed out	1028 ms	7248 KB	Time limit exceeded
87	Execution timed out	1028 ms	7044 KB	Time limit exceeded
88	Execution timed out	1072 ms	7252 KB	Time limit exceeded
89	Execution timed out	1020 ms	7248 KB	Time limit exceeded
90	Execution timed out	1049 ms	7404 KB	Time limit exceeded
91	Execution timed out	1044 ms	7136 KB	Time limit exceeded
92	Execution timed out	1051 ms	7468 KB	Time limit exceeded