답안 #886615

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
886615 2023-12-12T12:27:54 Z gnu Mecho (IOI09_mecho) C++14
18 / 100
126 ms 22692 KB
#include <bits/stdc++.h>
using namespace std;
int n, S;
vector<string> board;
vector<vector<int>> vis;
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
struct point{
    int i, j;
    point(int i, int j) {
        this->i = i;
        this->j = j;
    }
};
void solve()
{
    n, S; cin >> n >> S;
    board = vector<string>(n);
    vis = vector<vector<int>> (n, vector<int> (n));
    for (int i = 0; i < n; ++i) cin >> board[i];
    point mecho(0,0), home(0,0);
    vector<point> honey;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (board[i][j] == 'H') honey.emplace_back(i, j);
            else if (board[i][j] == 'M') mecho = {i, j};
            else if (board[i][j] == 'D') home = {i, j};
        }
    }
    queue<point> mq;
    vector<vector<int>> dist(n, vector<int> (n, 0   ));
    for (auto x : honey) {
        mq.push(x);
        vis[x.i][x.j] = 1;
        dist[x.i][x.j] = 0;
    }
    while (!mq.empty()) {
        point u = mq.front();
        mq.pop();
        for (int i = 0; i < 4; ++i) {
            if (u.i + dx[i] < 0 || u.i + dx[i] >= n || u.j + dy[i] < 0 || u.j + dy[i] >= n || vis[u.i+dx[i]][u.j+dy[i]] || (board[u.i+dx[i]][u.j+dy[i]] != 'G' && board[u.i+dx[i]][u.j+dy[i]] != 'M')) continue;
            mq.emplace(u.i + dx[i], u.j + dy[i]);
            vis[u.i + dx[i]][u.j + dy[i]] = 1;
            dist[u.i + dx[i]][u.j + dy[i]] = dist[u.i][u.j] + 1;
        }
    }
//    for (auto &x : dist)
//    {
//        for (auto y : x) cout << y << ' ';
//        cout << '\n';
//    }

    int l = -1, r = 1e9;
//    return;
    while (l + 1 < r) {
        vector<vector<int>> md(n, vector<int> (n));
        int m = (l + r) / 2;
        vis = vector<vector<int>> (n, vector<int> (n));
        queue<point> q;
        q.emplace(mecho.i, mecho.j);
        vis[mecho.i][mecho.j] = 1;
        if (m >= dist[mecho.i][mecho.j]) q.pop();
        while (!q.empty()) {
            point u = q.front();

            q.pop();
            for (int i = 0; i < 4; ++i) {
                int ni = u.i + dx[i], nj = u.j + dy[i];
                if (((md[u.i][u.j]+1) / S >= (dist[u.i][u.j] - m))) continue;
                if (u.i + dx[i] < 0 || u.i + dx[i] >= n || u.j + dy[i] < 0 || u.j + dy[i] >= n || vis[u.i+dx[i]][u.j+dy[i]] || (board[u.i+dx[i]][u.j+dy[i]] != 'G' && board[u.i+dx[i]][u.j+dy[i]] != 'M')) continue;
                q.emplace(ni, nj);
                md[ni][nj] = md[u.i][u.j] + 1;
                vis[ni][nj] = 1;
            }
        }
        bool ok = false;
        for (int i = 0; i < 4; ++i) {
            point u = home;
            if (((md[u.i][u.j]+1) / S >= (dist[u.i + dx[i]][u.j + dy[i]] - m))) continue;
            if (u.i + dx[i] < 0 || u.i + dx[i] >= n || u.j + dy[i] < 0 || u.j + dy[i] >= n || (board[u.i+dx[i]][u.j+dy[i]] != 'G' && board[u.i+dx[i]][u.j+dy[i]] != 'M')) continue;
            if (vis[home.i + dx[i]][home.j+dy[i]]) ok = true;
        }
        if (ok) {
            l = m;
        } else r = m;

    }
    cout << l;

}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    solve();
}

Compilation message

mecho.cpp: In function 'void solve()':
mecho.cpp:17:5: warning: left operand of comma operator has no effect [-Wunused-value]
   17 |     n, S; cin >> n >> S;
      |     ^
mecho.cpp:17:9: warning: right operand of comma operator has no effect [-Wunused-value]
   17 |     n, S; cin >> n >> S;
      |         ^
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 756 KB Execution killed with signal 11
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Runtime error 1 ms 348 KB Execution killed with signal 11
4 Runtime error 1 ms 348 KB Execution killed with signal 11
5 Correct 0 ms 348 KB Output is correct
6 Runtime error 1 ms 604 KB Execution killed with signal 11
7 Incorrect 104 ms 11356 KB Output isn't correct
8 Runtime error 1 ms 600 KB Execution killed with signal 11
9 Runtime error 1 ms 604 KB Execution killed with signal 11
10 Runtime error 1 ms 492 KB Execution killed with signal 11
11 Runtime error 1 ms 604 KB Execution killed with signal 11
12 Runtime error 1 ms 604 KB Execution killed with signal 11
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Runtime error 1 ms 604 KB Execution killed with signal 11
16 Correct 0 ms 348 KB Output is correct
17 Runtime error 1 ms 604 KB Execution killed with signal 11
18 Correct 1 ms 344 KB Output is correct
19 Runtime error 1 ms 604 KB Execution killed with signal 11
20 Correct 0 ms 348 KB Output is correct
21 Runtime error 1 ms 604 KB Execution killed with signal 11
22 Correct 1 ms 348 KB Output is correct
23 Runtime error 1 ms 600 KB Execution killed with signal 11
24 Correct 0 ms 348 KB Output is correct
25 Runtime error 1 ms 604 KB Execution killed with signal 11
26 Correct 1 ms 348 KB Output is correct
27 Runtime error 1 ms 604 KB Execution killed with signal 11
28 Correct 1 ms 348 KB Output is correct
29 Runtime error 1 ms 604 KB Execution killed with signal 11
30 Correct 1 ms 348 KB Output is correct
31 Runtime error 1 ms 604 KB Execution killed with signal 11
32 Correct 1 ms 348 KB Output is correct
33 Runtime error 4 ms 4700 KB Execution killed with signal 11
34 Correct 7 ms 2548 KB Output is correct
35 Runtime error 6 ms 4824 KB Execution killed with signal 11
36 Runtime error 6 ms 5980 KB Execution killed with signal 11
37 Correct 8 ms 3164 KB Output is correct
38 Runtime error 6 ms 5932 KB Execution killed with signal 11
39 Runtime error 7 ms 7424 KB Execution killed with signal 11
40 Correct 10 ms 3884 KB Output is correct
41 Runtime error 7 ms 7516 KB Execution killed with signal 11
42 Runtime error 8 ms 9052 KB Execution killed with signal 11
43 Correct 11 ms 4724 KB Output is correct
44 Runtime error 9 ms 9048 KB Execution killed with signal 11
45 Runtime error 10 ms 10840 KB Execution killed with signal 11
46 Correct 14 ms 5612 KB Output is correct
47 Runtime error 14 ms 10928 KB Execution killed with signal 11
48 Runtime error 14 ms 13084 KB Execution killed with signal 11
49 Correct 18 ms 6608 KB Output is correct
50 Runtime error 13 ms 12888 KB Execution killed with signal 11
51 Runtime error 13 ms 14940 KB Execution killed with signal 11
52 Correct 21 ms 7668 KB Output is correct
53 Runtime error 15 ms 14936 KB Execution killed with signal 11
54 Runtime error 15 ms 17244 KB Execution killed with signal 11
55 Correct 25 ms 8772 KB Output is correct
56 Runtime error 18 ms 17244 KB Execution killed with signal 11
57 Runtime error 18 ms 19808 KB Execution killed with signal 11
58 Correct 24 ms 10016 KB Output is correct
59 Runtime error 20 ms 19860 KB Execution killed with signal 11
60 Runtime error 20 ms 22364 KB Execution killed with signal 11
61 Correct 29 ms 11312 KB Output is correct
62 Runtime error 23 ms 22352 KB Execution killed with signal 11
63 Runtime error 30 ms 22356 KB Execution killed with signal 11
64 Runtime error 30 ms 22340 KB Execution killed with signal 11
65 Runtime error 29 ms 22468 KB Execution killed with signal 11
66 Runtime error 30 ms 22360 KB Execution killed with signal 11
67 Runtime error 29 ms 22352 KB Execution killed with signal 11
68 Runtime error 32 ms 22380 KB Execution killed with signal 11
69 Runtime error 31 ms 22432 KB Execution killed with signal 11
70 Runtime error 32 ms 22620 KB Execution killed with signal 11
71 Runtime error 36 ms 22612 KB Execution killed with signal 11
72 Runtime error 33 ms 22620 KB Execution killed with signal 11
73 Runtime error 28 ms 22612 KB Execution killed with signal 11
74 Runtime error 27 ms 22620 KB Execution killed with signal 11
75 Runtime error 27 ms 22632 KB Execution killed with signal 11
76 Runtime error 27 ms 22692 KB Execution killed with signal 11
77 Runtime error 27 ms 22668 KB Execution killed with signal 11
78 Correct 101 ms 11476 KB Output is correct
79 Incorrect 73 ms 11384 KB Output isn't correct
80 Incorrect 76 ms 11304 KB Output isn't correct
81 Incorrect 88 ms 11412 KB Output isn't correct
82 Incorrect 95 ms 11384 KB Output isn't correct
83 Incorrect 98 ms 11336 KB Output isn't correct
84 Incorrect 87 ms 11348 KB Output isn't correct
85 Incorrect 102 ms 11424 KB Output isn't correct
86 Incorrect 93 ms 11332 KB Output isn't correct
87 Incorrect 90 ms 11376 KB Output isn't correct
88 Incorrect 108 ms 11356 KB Output isn't correct
89 Incorrect 102 ms 11176 KB Output isn't correct
90 Incorrect 107 ms 11360 KB Output isn't correct
91 Incorrect 106 ms 11396 KB Output isn't correct
92 Incorrect 126 ms 11360 KB Output isn't correct