답안 #978390

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978390	2024-05-09T07:46:32 Z	Bodisha	Mecho (IOI09_mecho)	C++17	11 / 100	1000 ms	7336 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 = 5 * 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

11.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	2396 KB	Output isn't correct
2	Incorrect	0 ms	2396 KB	Output isn't correct
3	Incorrect	1 ms	2396 KB	Output isn't correct
4	Incorrect	1 ms	2396 KB	Output isn't correct
5	Correct	1 ms	2396 KB	Output is correct
6	Incorrect	1 ms	2392 KB	Output isn't correct
7	Execution timed out	1094 ms	7068 KB	Time limit exceeded
8	Incorrect	1 ms	2392 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	1 ms	4696 KB	Output is correct
13	Correct	2 ms	2652 KB	Output is correct
14	Incorrect	3 ms	4856 KB	Output isn't correct
15	Incorrect	1 ms	2392 KB	Output isn't correct
16	Correct	1 ms	2392 KB	Output is 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	1 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	2 ms	4696 KB	Output isn't correct
26	Incorrect	1 ms	4696 KB	Output isn't correct
27	Incorrect	2 ms	4700 KB	Output isn't correct
28	Incorrect	1 ms	4700 KB	Output isn't correct
29	Incorrect	2 ms	4700 KB	Output isn't correct
30	Incorrect	2 ms	4700 KB	Output isn't correct
31	Incorrect	2 ms	4700 KB	Output isn't correct
32	Incorrect	2 ms	4612 KB	Output isn't correct
33	Incorrect	34 ms	5208 KB	Output isn't correct
34	Incorrect	20 ms	5208 KB	Output isn't correct
35	Correct	338 ms	5460 KB	Output is correct
36	Incorrect	45 ms	5208 KB	Output isn't correct
37	Incorrect	25 ms	5208 KB	Output isn't correct
38	Correct	333 ms	5760 KB	Output is correct
39	Incorrect	61 ms	5408 KB	Output isn't correct
40	Incorrect	34 ms	5212 KB	Output isn't correct
41	Correct	375 ms	5648 KB	Output is correct
42	Incorrect	76 ms	5484 KB	Output isn't correct
43	Incorrect	42 ms	5468 KB	Output isn't correct
44	Correct	414 ms	5668 KB	Output is correct
45	Incorrect	90 ms	5468 KB	Output isn't correct
46	Incorrect	50 ms	5464 KB	Output isn't correct
47	Correct	525 ms	5712 KB	Output is correct
48	Incorrect	108 ms	5720 KB	Output isn't correct
49	Incorrect	60 ms	5756 KB	Output isn't correct
50	Correct	628 ms	6228 KB	Output is correct
51	Incorrect	128 ms	5980 KB	Output isn't correct
52	Incorrect	71 ms	5980 KB	Output isn't correct
53	Correct	593 ms	6536 KB	Output is correct
54	Incorrect	145 ms	6236 KB	Output isn't correct
55	Incorrect	81 ms	6236 KB	Output isn't correct
56	Correct	551 ms	6516 KB	Output is correct
57	Incorrect	170 ms	6232 KB	Output isn't correct
58	Incorrect	98 ms	6472 KB	Output isn't correct
59	Correct	524 ms	6776 KB	Output is correct
60	Incorrect	192 ms	6692 KB	Output isn't correct
61	Incorrect	105 ms	6488 KB	Output isn't correct
62	Incorrect	279 ms	6960 KB	Output isn't correct
63	Incorrect	298 ms	6696 KB	Output isn't correct
64	Incorrect	305 ms	6492 KB	Output isn't correct
65	Incorrect	306 ms	6712 KB	Output isn't correct
66	Incorrect	314 ms	6716 KB	Output isn't correct
67	Correct	306 ms	6700 KB	Output is correct
68	Incorrect	253 ms	6724 KB	Output isn't correct
69	Incorrect	257 ms	6748 KB	Output isn't correct
70	Incorrect	257 ms	6748 KB	Output isn't correct
71	Incorrect	251 ms	6748 KB	Output isn't correct
72	Correct	282 ms	6728 KB	Output is correct
73	Correct	740 ms	7336 KB	Output is correct
74	Execution timed out	1074 ms	7232 KB	Time limit exceeded
75	Execution timed out	1062 ms	7240 KB	Time limit exceeded
76	Execution timed out	1022 ms	7016 KB	Time limit exceeded
77	Execution timed out	1012 ms	7192 KB	Time limit exceeded
78	Execution timed out	1069 ms	7200 KB	Time limit exceeded
79	Execution timed out	1047 ms	7288 KB	Time limit exceeded
80	Execution timed out	1044 ms	7000 KB	Time limit exceeded
81	Execution timed out	1064 ms	7236 KB	Time limit exceeded
82	Execution timed out	1038 ms	6984 KB	Time limit exceeded
83	Incorrect	922 ms	7264 KB	Output isn't correct
84	Correct	910 ms	6920 KB	Output is correct
85	Incorrect	765 ms	7036 KB	Output isn't correct
86	Incorrect	965 ms	7048 KB	Output isn't correct
87	Execution timed out	1016 ms	7036 KB	Time limit exceeded
88	Execution timed out	1083 ms	7240 KB	Time limit exceeded
89	Execution timed out	1037 ms	6888 KB	Time limit exceeded
90	Execution timed out	1081 ms	7172 KB	Time limit exceeded
91	Execution timed out	1022 ms	6860 KB	Time limit exceeded
92	Execution timed out	1016 ms	7280 KB	Time limit exceeded