답안 #483953

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483953	2021-11-01T15:26:09 Z	nehasane	Mecho (IOI09_mecho)	C++14	10 / 100	1000 ms	5828 KB

mecho

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 800;
vector <string> field(MAX_N);
bool bees_visited[MAX_N][MAX_N], mecho_visited[MAX_N][MAX_N];
int dis[MAX_N][MAX_N];
queue <pair <int, int>> mecho_q, bees_q;
int n, s;
bool valid_sq(int x, int y, bool mecho){
    if (x >= 0 && x < n && y >= 0 && y < n){
        if (mecho && (field[x][y] == 'G' || field[x][y] == 'D' || field[x][y] == 'M'))
            return true;
        else if (!mecho && (field[x][y] == 'G' || field[x][y] == 'H'))
            return true;
        return false;
    }
    return false;
}
void move_bees(int x, int y, bool add){
    if (valid_sq(x-1, y, false) && !bees_visited[x-1][y]){
        if (add)
            bees_q.push({x-1, y});
        bees_visited[x-1][y] = true;
    }
    if (valid_sq(x+1, y, false) && !bees_visited[x+1][y]){
        if (add)
            bees_q.push({x+1, y});
        bees_visited[x+1][y] = true;
    }
    if (valid_sq(x, y-1, false) && !bees_visited[x][y-1]){
        if (add)
            bees_q.push({x, y-1});
        bees_visited[x][y-1] = true;
    }
    if (valid_sq(x, y+1, false) && !bees_visited[x][y+1]){
        if (add)
            bees_q.push({x, y+1});
        bees_visited[x][y+1] = true;
    }
}
void move_mecho(int x, int y, bool add){
    if (valid_sq(x-1, y, true) && !mecho_visited[x-1][y] && !bees_visited[x-1][y]){
        mecho_visited[x-1][y] = true;
        if (add)
            mecho_q.push({x-1, y});
    }
    if (valid_sq(x+1, y, true) && !mecho_visited[x+1][y] && !bees_visited[x+1][y]){
        mecho_visited[x+1][y] = true;
        if (add)
            mecho_q.push({x+1, y});
    }
    if (valid_sq(x, y-1, true) && !mecho_visited[x][y-1] && !bees_visited[x][y-1]){
        mecho_visited[x][y-1] = true;
        if (add)
            mecho_q.push({x, y-1});
    }
    if (valid_sq(x, y+1, true) && !mecho_visited[x][y+1] && !bees_visited[x][y+1]){
        mecho_visited[x][y+1] = true;
        if (add)
            mecho_q.push({x, y+1});
    }
}
void mecho_bfs(){
    while (!mecho_q.empty() && dis[mecho_q.front().first][mecho_q.front().second] < s){
        int x = mecho_q.front().first, y = mecho_q.front().second;
        mecho_q.pop();
        if (dis[x][y] >= s){
            mecho_q.push({x, y});
            continue;
        }
        if (valid_sq(x-1, y, true) && !mecho_visited[x-1][y] && !bees_visited[x-1][y] && dis[x][y] + 1 <= s){
            mecho_visited[x-1][y] = true;
            mecho_q.push({x-1, y});
            dis[x-1][y] = dis[x][y] + 1;
        }
        if (valid_sq(x+1, y, true) && !mecho_visited[x+1][y] && !bees_visited[x+1][y] && dis[x][y] + 1 <= s){
            mecho_visited[x+1][y] = true;
            mecho_q.push({x+1, y});
            dis[x+1][y] = dis[x][y] + 1;
        }
        if (valid_sq(x, y-1, true) && !mecho_visited[x][y-1] && !bees_visited[x][y-1] && dis[x][y] + 1 <= s){
            mecho_visited[x][y-1] = true;
            mecho_q.push({x, y-1});
            dis[x][y-1] = dis[x][y] + 1;
        }
        if (valid_sq(x, y+1, true) && !mecho_visited[x][y+1] && !bees_visited[x][y+1] && dis[x][y] + 1 <= s){
            mecho_visited[x][y+1] = true;
            mecho_q.push({x, y+1});
            dis[x][y+1] = dis[x][y] + 1;
        }
    }
}
int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    cin >> n >> s;
    for (int i = 0; i < n; i++)
        cin >> field[i];
    vector <pair <int, int>> hives;
    int startx, starty, home_x, home_y;
    //find Mecho's position
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if (field[i][j] == 'M'){
                startx = i;
                starty = j;
            }else if (field[i][j] == 'H'){
                hives.push_back({i, j});
            }else if (field[i][j] == 'D'){
                home_x = i;
                home_y = j;
            }
        }
    }
    int l = 0, r = n + n - 2;
    while (l <= r){
        int eating_time = (l + r) / 2;
        memset(bees_visited, false, sizeof(bees_visited));
        memset(mecho_visited, false, sizeof(mecho_visited));
        //simulate
        //move only bees, since mecho is eating
        for (auto i : hives){
            bees_q.push({i.first, i.second});
            bees_visited[i.first][i.second] = true;
        }

        for (int i = 0; i < eating_time; i++){
            int si = bees_q.size();
            for (int j = 0; j < si; j++){
                move_bees(bees_q.front().first, bees_q.front().second, true);
                bees_q.pop();
            }
        }    
        //move mecho and bees
        mecho_q.push({startx, starty});
        for (int i = eating_time; i < 2 * n - 2; i++){            
            mecho_bfs();
            memset(dis, 0, sizeof(dis));
            int si = bees_q.size();
            for (int j = 0; j < si; j++){
                move_bees(bees_q.front().first, bees_q.front().second, true);
                bees_q.pop();
            }
        }
        if (mecho_visited[home_x][home_y])
            l = eating_time + 1;
        else
            r = eating_time - 1;
        //empty both queues
        while (!bees_q.empty())
            bees_q.pop();
        while (!mecho_q.empty())
            mecho_q.pop();
    }
    cout << r << '\n';
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:146:41: warning: 'home_y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  146 |         if (mecho_visited[home_x][home_y])
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
mecho.cpp:146:41: warning: 'home_x' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1

10.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	4044 KB	Output isn't correct
2	Incorrect	3 ms	4044 KB	Output isn't correct
3	Incorrect	3 ms	4044 KB	Output isn't correct
4	Incorrect	4 ms	4044 KB	Output isn't correct
5	Correct	4 ms	4044 KB	Output is correct
6	Correct	6 ms	4044 KB	Output is correct
7	Execution timed out	1084 ms	5508 KB	Time limit exceeded
8	Incorrect	9 ms	4044 KB	Output isn't correct
9	Correct	8 ms	4076 KB	Output is correct
10	Correct	8 ms	4084 KB	Output is correct
11	Correct	7 ms	4008 KB	Output is correct
12	Incorrect	9 ms	4084 KB	Output isn't correct
13	Incorrect	35 ms	4068 KB	Output isn't correct
14	Correct	37 ms	4164 KB	Output is correct
15	Incorrect	4 ms	4044 KB	Output isn't correct
16	Incorrect	4 ms	4040 KB	Output isn't correct
17	Incorrect	4 ms	4044 KB	Output isn't correct
18	Incorrect	5 ms	4044 KB	Output isn't correct
19	Incorrect	5 ms	4044 KB	Output isn't correct
20	Incorrect	5 ms	4044 KB	Output isn't correct
21	Incorrect	6 ms	4044 KB	Output isn't correct
22	Incorrect	8 ms	4044 KB	Output isn't correct
23	Incorrect	9 ms	4084 KB	Output isn't correct
24	Incorrect	11 ms	4080 KB	Output isn't correct
25	Incorrect	9 ms	4044 KB	Output isn't correct
26	Incorrect	12 ms	4044 KB	Output isn't correct
27	Incorrect	10 ms	4088 KB	Output isn't correct
28	Incorrect	10 ms	4044 KB	Output isn't correct
29	Incorrect	10 ms	4096 KB	Output isn't correct
30	Incorrect	13 ms	4108 KB	Output isn't correct
31	Incorrect	10 ms	4044 KB	Output isn't correct
32	Incorrect	11 ms	4088 KB	Output isn't correct
33	Incorrect	47 ms	4356 KB	Output isn't correct
34	Incorrect	49 ms	4328 KB	Output isn't correct
35	Correct	355 ms	4348 KB	Output is correct
36	Incorrect	53 ms	4300 KB	Output isn't correct
37	Incorrect	76 ms	4300 KB	Output isn't correct
38	Correct	474 ms	4500 KB	Output is correct
39	Incorrect	63 ms	4428 KB	Output isn't correct
40	Incorrect	88 ms	4468 KB	Output isn't correct
41	Correct	540 ms	4540 KB	Output is correct
42	Incorrect	66 ms	4684 KB	Output isn't correct
43	Incorrect	79 ms	4684 KB	Output isn't correct
44	Correct	605 ms	4908 KB	Output is correct
45	Incorrect	79 ms	4864 KB	Output isn't correct
46	Incorrect	82 ms	4812 KB	Output isn't correct
47	Correct	776 ms	4884 KB	Output is correct
48	Incorrect	88 ms	4940 KB	Output isn't correct
49	Incorrect	95 ms	5068 KB	Output isn't correct
50	Correct	750 ms	4992 KB	Output is correct
51	Incorrect	88 ms	5068 KB	Output isn't correct
52	Incorrect	134 ms	5068 KB	Output isn't correct
53	Correct	868 ms	5156 KB	Output is correct
54	Incorrect	96 ms	5196 KB	Output isn't correct
55	Incorrect	128 ms	5120 KB	Output isn't correct
56	Correct	998 ms	5216 KB	Output is correct
57	Incorrect	106 ms	5452 KB	Output isn't correct
58	Incorrect	121 ms	5332 KB	Output isn't correct
59	Execution timed out	1081 ms	5328 KB	Time limit exceeded
60	Incorrect	106 ms	5452 KB	Output isn't correct
61	Incorrect	137 ms	5452 KB	Output isn't correct
62	Execution timed out	1084 ms	5400 KB	Time limit exceeded
63	Execution timed out	1084 ms	5452 KB	Time limit exceeded
64	Correct	686 ms	5380 KB	Output is correct
65	Correct	937 ms	5476 KB	Output is correct
66	Execution timed out	1088 ms	5424 KB	Time limit exceeded
67	Execution timed out	1044 ms	5452 KB	Time limit exceeded
68	Execution timed out	1069 ms	5444 KB	Time limit exceeded
69	Execution timed out	1087 ms	5472 KB	Time limit exceeded
70	Execution timed out	1084 ms	5424 KB	Time limit exceeded
71	Execution timed out	1088 ms	5444 KB	Time limit exceeded
72	Incorrect	371 ms	5484 KB	Output isn't correct
73	Execution timed out	1044 ms	5704 KB	Time limit exceeded
74	Execution timed out	1061 ms	5828 KB	Time limit exceeded
75	Execution timed out	1008 ms	5828 KB	Time limit exceeded
76	Execution timed out	1091 ms	5700 KB	Time limit exceeded
77	Execution timed out	1016 ms	5828 KB	Time limit exceeded
78	Execution timed out	1073 ms	5716 KB	Time limit exceeded
79	Execution timed out	1089 ms	5700 KB	Time limit exceeded
80	Execution timed out	1044 ms	5824 KB	Time limit exceeded
81	Execution timed out	1094 ms	5700 KB	Time limit exceeded
82	Execution timed out	1086 ms	5708 KB	Time limit exceeded
83	Execution timed out	1086 ms	5680 KB	Time limit exceeded
84	Execution timed out	1090 ms	5628 KB	Time limit exceeded
85	Execution timed out	1085 ms	5636 KB	Time limit exceeded
86	Execution timed out	1089 ms	5612 KB	Time limit exceeded
87	Execution timed out	1083 ms	5572 KB	Time limit exceeded
88	Execution timed out	1091 ms	5572 KB	Time limit exceeded
89	Execution timed out	1081 ms	5576 KB	Time limit exceeded
90	Execution timed out	1090 ms	5572 KB	Time limit exceeded
91	Execution timed out	1089 ms	5548 KB	Time limit exceeded
92	Execution timed out	1087 ms	5584 KB	Time limit exceeded