답안 #978134

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978134	2024-05-08T22:15:21 Z	Bodisha	Mecho (IOI09_mecho)	C++17	54 / 100	279 ms	7248 KB

mecho

#include <bits/stdc++.h>
#define MAX_N 801
#define UNVISITED 0
#define BEAR 1
#define BEE 2

using namespace std;

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

bool check(int t) {
    pair<int, int> mecho_pos;
    pair<int, int> home_pos;
    vector<pair<int, int>> hive_edges;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            visited[i][j] = UNVISITED;
            beed[i][j] = -69;
            if(grid[i][j] == 'H') {
                hive_edges.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>> beeq;
    vector<pair<int, int>> bees_edge;
    for(auto iter : hive_edges) {
        visited[iter.first][iter.second] = BEE;
        beed[iter.first][iter.second] = 0;
        beeq.push(iter);
    }
    while(!beeq.empty()) {
        pair<int, int> curr = beeq.front();
        beeq.pop();
        if(beed[curr.first][curr.second] == t) {
            bees_edge.push_back(curr);
            continue;
        }
        if(visited[curr.first + 1][curr.second] == UNVISITED && (grid[curr.first + 1][curr.second] == 'G' || grid[curr.first + 1][curr.second] == 'M')) {
            visited[curr.first + 1][curr.second] = BEE;
            beed[curr.first + 1][curr.second] = beed[curr.first][curr.second] + 1;
            beeq.push({curr.first + 1, curr.second});
        }
        if(visited[curr.first - 1][curr.second] == UNVISITED && (grid[curr.first - 1][curr.second] == 'G' || grid[curr.first - 1][curr.second] == 'M')) {
            visited[curr.first - 1][curr.second] = BEE;
            beed[curr.first - 1][curr.second] = beed[curr.first][curr.second] + 1;
            beeq.push({curr.first - 1, curr.second});
        }
        if(visited[curr.first][curr.second + 1] == UNVISITED && (grid[curr.first][curr.second + 1] == 'G' || grid[curr.first][curr.second + 1] == 'M')) {
            visited[curr.first][curr.second + 1] = BEE;
            beed[curr.first][curr.second + 1] = beed[curr.first][curr.second] + 1;
            beeq.push({curr.first, curr.second + 1});
        }
        if(visited[curr.first][curr.second - 1] == UNVISITED && (grid[curr.first][curr.second - 1] == 'G' || grid[curr.first][curr.second - 1] == 'M')) {
            visited[curr.first][curr.second - 1] = BEE;
            beed[curr.first][curr.second - 1] = beed[curr.first][curr.second] + 1;
            beeq.push({curr.first, curr.second - 1});
        }
    }
    if(visited[mecho_pos.first][mecho_pos.second] == BEE) {
        return false;
    }
    set<pair<int, int>> mecho_edge;
    mecho_edge.insert(mecho_pos);
    bool found = false;
    while(!found) {
        if(mecho_edge.size() == 0) {
            return false;
        }
        queue<pair<pair<int, int>, int>> q; // mecho queue
        for(auto iter : mecho_edge) {
            visited[iter.first][iter.second] = BEAR;
            q.push({iter, 0});
        }
        mecho_edge.clear();
        while(!q.empty()) {
            pair<pair<int, int>, int> curr = q.front();
            q.pop();
            if(curr.first.first + 1 < n && visited[curr.first.first + 1][curr.first.second] == UNVISITED && (grid[curr.first.first + 1][curr.first.second] == 'G' || grid[curr.first.first + 1][curr.first.second] == 'D')){
                if(curr.second == s - 1) {
                    visited[curr.first.first + 1][curr.first.second] = BEAR;
                    mecho_edge.insert({curr.first.first + 1, curr.first.second});
                } else {
                    visited[curr.first.first + 1][curr.first.second] = BEAR;
                    q.push({{curr.first.first + 1, curr.first.second}, curr.second + 1});
                }
            }
            if(curr.first.first - 1 >= 0 && visited[curr.first.first - 1][curr.first.second] == UNVISITED && (grid[curr.first.first - 1][curr.first.second] == 'G' || grid[curr.first.first - 1][curr.first.second] == 'D')){
                if(curr.second == s - 1) {
                    visited[curr.first.first - 1][curr.first.second] = BEAR;
                    mecho_edge.insert({curr.first.first - 1, curr.first.second});
                } else {
                    visited[curr.first.first - 1][curr.first.second] = BEAR;
                    q.push({{curr.first.first - 1, curr.first.second}, curr.second + 1});
                }
            }
            if(curr.first.second + 1 < n && visited[curr.first.first][curr.first.second + 1] == UNVISITED && (grid[curr.first.first][curr.first.second + 1] == 'G' || grid[curr.first.first][curr.first.second + 1] == 'D')){
                if(curr.second == s - 1) {
                    visited[curr.first.first][curr.first.second + 1] = BEAR;
                    mecho_edge.insert({curr.first.first, curr.first.second + 1});
                } else {
                    visited[curr.first.first][curr.first.second + 1] = BEAR;
                    q.push({{curr.first.first, curr.first.second + 1}, curr.second + 1});
                }
            }
            if(curr.first.second - 1 >= 0 && visited[curr.first.first][curr.first.second - 1] == UNVISITED && (grid[curr.first.first][curr.first.second - 1] == 'G' || grid[curr.first.first][curr.first.second - 1] == 'D')){
                if(curr.second == s - 1) {
                    visited[curr.first.first][curr.first.second - 1] = BEAR;
                    mecho_edge.insert({curr.first.first, curr.first.second - 1});
                } else {
                    visited[curr.first.first][curr.first.second - 1] = BEAR;
                    q.push({{curr.first.first, curr.first.second - 1}, curr.second + 1});
                }
            }
        }
        if(visited[home_pos.first][home_pos.second] == BEAR) {
            found = true;
            break;
        }
        vector<pair<int, int>> tmpedge;
        for(auto iter : bees_edge) {
            if(iter.first + 1 < n && visited[iter.first + 1][iter.second] == UNVISITED && grid[iter.first + 1][iter.second] == 'G') {
                visited[iter.first + 1][iter.second] = true;
                tmpedge.push_back({iter.first + 1, iter.second});
            }
            if(iter.first - 1 >= 0 && visited[iter.first - 1][iter.second] == UNVISITED && grid[iter.first - 1][iter.second] == 'G') {
                visited[iter.first - 1][iter.second] = true;
                tmpedge.push_back({iter.first - 1, iter.second});
            }
            if(iter.second + 1 < n && visited[iter.first][iter.second + 1] == UNVISITED && grid[iter.first][iter.second + 1] == 'G') {
                visited[iter.first][iter.second + 1] = true;
                tmpedge.push_back({iter.first, iter.second + 1});
            }
            if(iter.second - 1 >= 0 && visited[iter.first][iter.second - 1] == UNVISITED && grid[iter.first][iter.second - 1] == 'G') {
                visited[iter.first][iter.second - 1] = true;
                tmpedge.push_back({iter.first, iter.second - 1});
            }
        }
        bees_edge.clear();
        bees_edge = tmpedge;
    }
    if(found) {
        return true;
    } else {
        return false;
    }
}

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;
    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

54.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	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	Correct	1 ms	2396 KB	Output is correct
7	Correct	207 ms	6496 KB	Output is correct
8	Incorrect	1 ms	2396 KB	Output isn't correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	1 ms	4700 KB	Output is correct
13	Correct	1 ms	2652 KB	Output is correct
14	Correct	2 ms	4696 KB	Output is correct
15	Incorrect	1 ms	2392 KB	Output isn't correct
16	Correct	1 ms	2484 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	2396 KB	Output isn't correct
20	Correct	1 ms	2396 KB	Output is correct
21	Incorrect	1 ms	2652 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	1 ms	4700 KB	Output is correct
27	Incorrect	1 ms	4700 KB	Output isn't correct
28	Correct	1 ms	4700 KB	Output is correct
29	Incorrect	1 ms	4700 KB	Output isn't correct
30	Correct	1 ms	4700 KB	Output is correct
31	Incorrect	2 ms	4700 KB	Output isn't correct
32	Correct	1 ms	4700 KB	Output is correct
33	Incorrect	21 ms	4932 KB	Output isn't correct
34	Correct	17 ms	4952 KB	Output is correct
35	Correct	21 ms	4956 KB	Output is correct
36	Incorrect	30 ms	4956 KB	Output isn't correct
37	Correct	22 ms	5024 KB	Output is correct
38	Correct	30 ms	4956 KB	Output is correct
39	Incorrect	36 ms	5072 KB	Output isn't correct
40	Correct	25 ms	4956 KB	Output is correct
41	Correct	37 ms	4952 KB	Output is correct
42	Incorrect	48 ms	4956 KB	Output isn't correct
43	Correct	35 ms	4952 KB	Output is correct
44	Correct	46 ms	5112 KB	Output is correct
45	Incorrect	54 ms	4952 KB	Output isn't correct
46	Correct	37 ms	5116 KB	Output is correct
47	Correct	55 ms	5144 KB	Output is correct
48	Incorrect	64 ms	5212 KB	Output isn't correct
49	Correct	54 ms	5212 KB	Output is correct
50	Correct	70 ms	5288 KB	Output is correct
51	Incorrect	75 ms	5464 KB	Output isn't correct
52	Correct	58 ms	5464 KB	Output is correct
53	Correct	78 ms	5512 KB	Output is correct
54	Incorrect	89 ms	5672 KB	Output isn't correct
55	Correct	63 ms	5464 KB	Output is correct
56	Correct	93 ms	5468 KB	Output is correct
57	Incorrect	100 ms	5724 KB	Output isn't correct
58	Correct	78 ms	5868 KB	Output is correct
59	Correct	108 ms	5900 KB	Output is correct
60	Incorrect	120 ms	6060 KB	Output isn't correct
61	Correct	86 ms	5932 KB	Output is correct
62	Correct	124 ms	6068 KB	Output is correct
63	Correct	252 ms	6332 KB	Output is correct
64	Correct	215 ms	6092 KB	Output is correct
65	Correct	248 ms	5980 KB	Output is correct
66	Incorrect	279 ms	6088 KB	Output isn't correct
67	Correct	274 ms	6108 KB	Output is correct
68	Correct	220 ms	6352 KB	Output is correct
69	Correct	197 ms	5980 KB	Output is correct
70	Correct	199 ms	6112 KB	Output is correct
71	Correct	222 ms	6100 KB	Output is correct
72	Correct	235 ms	5976 KB	Output is correct
73	Correct	146 ms	7248 KB	Output is correct
74	Correct	181 ms	6236 KB	Output is correct
75	Correct	201 ms	6404 KB	Output is correct
76	Correct	186 ms	6232 KB	Output is correct
77	Correct	178 ms	6384 KB	Output is correct
78	Correct	186 ms	7248 KB	Output is correct
79	Correct	177 ms	6236 KB	Output is correct
80	Correct	186 ms	6236 KB	Output is correct
81	Correct	189 ms	6724 KB	Output is correct
82	Correct	192 ms	6236 KB	Output is correct
83	Correct	193 ms	7116 KB	Output is correct
84	Correct	194 ms	6236 KB	Output is correct
85	Correct	195 ms	6232 KB	Output is correct
86	Correct	195 ms	6236 KB	Output is correct
87	Correct	196 ms	6552 KB	Output is correct
88	Correct	190 ms	6936 KB	Output is correct
89	Correct	178 ms	6232 KB	Output is correct
90	Correct	179 ms	6480 KB	Output is correct
91	Correct	179 ms	6488 KB	Output is correct
92	Correct	192 ms	6768 KB	Output is correct