oj.uz

답안 #886611

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
886611 2023-12-12T12:12:21 Z gnu Mecho (IOI09_mecho) C++17
18 / 100
 194 ms 12528 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]] == 'T') 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') 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][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 || board[u.i+dx[i]][u.j+dy[i]] != 'G') 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);
/*#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif*/
    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;
      |         ^

Subtask #1
18.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Incorrect 101 ms 11932 KB Output isn't correct
8 Correct 0 ms 344 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 1 ms 348 KB Output isn't correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Correct 0 ms 344 KB Output is correct
17 Incorrect 0 ms 344 KB Output isn't correct
18 Correct 1 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB Output isn't correct
20 Correct 1 ms 344 KB Output is correct
21 Incorrect 1 ms 348 KB Output isn't correct
22 Correct 0 ms 348 KB Output is correct
23 Incorrect 1 ms 348 KB Output isn't correct
24 Correct 1 ms 348 KB Output is correct
25 Incorrect 1 ms 452 KB Output isn't correct
26 Correct 1 ms 348 KB Output is correct
27 Incorrect 1 ms 456 KB Output isn't correct
28 Correct 1 ms 348 KB Output is correct
29 Incorrect 1 ms 600 KB Output isn't correct
30 Correct 1 ms 348 KB Output is correct
31 Incorrect 1 ms 348 KB Output isn't correct
32 Correct 1 ms 348 KB Output is correct
33 Incorrect 8 ms 2652 KB Output isn't correct
34 Correct 7 ms 2648 KB Output is correct
35 Incorrect 25 ms 2664 KB Output isn't correct
36 Incorrect 7 ms 3164 KB Output isn't correct
37 Correct 8 ms 3368 KB Output is correct
38 Incorrect 32 ms 3164 KB Output isn't correct
39 Incorrect 9 ms 4104 KB Output isn't correct
40 Correct 10 ms 4136 KB Output is correct
41 Incorrect 39 ms 4116 KB Output isn't correct
42 Incorrect 10 ms 4968 KB Output isn't correct
43 Correct 11 ms 4952 KB Output is correct
44 Incorrect 52 ms 4980 KB Output isn't correct
45 Incorrect 14 ms 5884 KB Output isn't correct
46 Correct 14 ms 5916 KB Output is correct
47 Incorrect 64 ms 5900 KB Output isn't correct
48 Incorrect 16 ms 6944 KB Output isn't correct
49 Correct 18 ms 6976 KB Output is correct
50 Incorrect 79 ms 6976 KB Output isn't correct
51 Incorrect 19 ms 8028 KB Output isn't correct
52 Correct 24 ms 8024 KB Output is correct
53 Incorrect 96 ms 8040 KB Output isn't correct
54 Incorrect 24 ms 9268 KB Output isn't correct
55 Correct 27 ms 9236 KB Output is correct
56 Incorrect 112 ms 9260 KB Output isn't correct
57 Incorrect 29 ms 10532 KB Output isn't correct
58 Correct 24 ms 10572 KB Output is correct
59 Incorrect 130 ms 10632 KB Output isn't correct
60 Incorrect 27 ms 11940 KB Output isn't correct
61 Correct 29 ms 12152 KB Output is correct
62 Incorrect 162 ms 12100 KB Output isn't correct
63 Incorrect 101 ms 11984 KB Output isn't correct
64 Incorrect 183 ms 12016 KB Output isn't correct
65 Correct 194 ms 11924 KB Output is correct
66 Correct 131 ms 11964 KB Output is correct
67 Correct 124 ms 12136 KB Output is correct
68 Correct 76 ms 11996 KB Output is correct
69 Incorrect 65 ms 12056 KB Output isn't correct
70 Correct 53 ms 11976 KB Output is correct
71 Correct 55 ms 12076 KB Output is correct
72 Correct 57 ms 12080 KB Output is correct
73 Correct 56 ms 12040 KB Output is correct
74 Incorrect 82 ms 12064 KB Output isn't correct
75 Incorrect 88 ms 12004 KB Output isn't correct
76 Incorrect 80 ms 12016 KB Output isn't correct
77 Incorrect 90 ms 11988 KB Output isn't correct
78 Correct 91 ms 12012 KB Output is correct
79 Incorrect 76 ms 12100 KB Output isn't correct
80 Incorrect 82 ms 11960 KB Output isn't correct
81 Incorrect 93 ms 12528 KB Output isn't correct
82 Incorrect 79 ms 12180 KB Output isn't correct
83 Incorrect 103 ms 12052 KB Output isn't correct
84 Incorrect 94 ms 12000 KB Output isn't correct
85 Incorrect 98 ms 12248 KB Output isn't correct
86 Incorrect 98 ms 12012 KB Output isn't correct
87 Incorrect 93 ms 12208 KB Output isn't correct
88 Incorrect 98 ms 11964 KB Output isn't correct
89 Incorrect 108 ms 12028 KB Output isn't correct
90 Incorrect 116 ms 11984 KB Output isn't correct
91 Incorrect 107 ms 12004 KB Output isn't correct
92 Incorrect 104 ms 11992 KB Output isn't correct