Submission #886613

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
886613	2023-12-12T12:25:59 Z	gnu	Mecho (IOI09_mecho)	C++17	0 / 100	3 ms	856 KB

mecho

#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' && 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);
 #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;
      |         ^
mecho.cpp: In function 'int main()':
mecho.cpp:96:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |      freopen("input.txt", "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:97:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |      freopen("output.txt", "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

0.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	2 ms	600 KB	Execution killed with signal 11
2	Runtime error	2 ms	604 KB	Execution killed with signal 11
3	Runtime error	2 ms	604 KB	Execution killed with signal 11
4	Runtime error	2 ms	604 KB	Execution killed with signal 11
5	Runtime error	2 ms	600 KB	Execution killed with signal 11
6	Runtime error	2 ms	604 KB	Execution killed with signal 11
7	Runtime error	2 ms	604 KB	Execution killed with signal 11
8	Runtime error	2 ms	604 KB	Execution killed with signal 11
9	Runtime error	2 ms	604 KB	Execution killed with signal 11
10	Runtime error	2 ms	604 KB	Execution killed with signal 11
11	Runtime error	2 ms	604 KB	Execution killed with signal 11
12	Runtime error	2 ms	600 KB	Execution killed with signal 11
13	Runtime error	2 ms	604 KB	Execution killed with signal 11
14	Runtime error	2 ms	604 KB	Execution killed with signal 11
15	Runtime error	2 ms	604 KB	Execution killed with signal 11
16	Runtime error	2 ms	604 KB	Execution killed with signal 11
17	Runtime error	2 ms	604 KB	Execution killed with signal 11
18	Runtime error	2 ms	604 KB	Execution killed with signal 11
19	Runtime error	2 ms	604 KB	Execution killed with signal 11
20	Runtime error	2 ms	604 KB	Execution killed with signal 11
21	Runtime error	2 ms	604 KB	Execution killed with signal 11
22	Runtime error	2 ms	600 KB	Execution killed with signal 11
23	Runtime error	2 ms	604 KB	Execution killed with signal 11
24	Runtime error	2 ms	856 KB	Execution killed with signal 11
25	Runtime error	2 ms	604 KB	Execution killed with signal 11
26	Runtime error	2 ms	604 KB	Execution killed with signal 11
27	Runtime error	2 ms	604 KB	Execution killed with signal 11
28	Runtime error	2 ms	604 KB	Execution killed with signal 11
29	Runtime error	2 ms	600 KB	Execution killed with signal 11
30	Runtime error	2 ms	524 KB	Execution killed with signal 11
31	Runtime error	2 ms	604 KB	Execution killed with signal 11
32	Runtime error	2 ms	604 KB	Execution killed with signal 11
33	Runtime error	2 ms	600 KB	Execution killed with signal 11
34	Runtime error	2 ms	604 KB	Execution killed with signal 11
35	Runtime error	2 ms	604 KB	Execution killed with signal 11
36	Runtime error	2 ms	604 KB	Execution killed with signal 11
37	Runtime error	2 ms	604 KB	Execution killed with signal 11
38	Runtime error	2 ms	604 KB	Execution killed with signal 11
39	Runtime error	2 ms	600 KB	Execution killed with signal 11
40	Runtime error	2 ms	604 KB	Execution killed with signal 11
41	Runtime error	2 ms	604 KB	Execution killed with signal 11
42	Runtime error	2 ms	604 KB	Execution killed with signal 11
43	Runtime error	2 ms	604 KB	Execution killed with signal 11
44	Runtime error	2 ms	604 KB	Execution killed with signal 11
45	Runtime error	2 ms	524 KB	Execution killed with signal 11
46	Runtime error	2 ms	804 KB	Execution killed with signal 11
47	Runtime error	2 ms	604 KB	Execution killed with signal 11
48	Runtime error	2 ms	604 KB	Execution killed with signal 11
49	Runtime error	2 ms	604 KB	Execution killed with signal 11
50	Runtime error	2 ms	604 KB	Execution killed with signal 11
51	Runtime error	2 ms	604 KB	Execution killed with signal 11
52	Runtime error	2 ms	604 KB	Execution killed with signal 11
53	Runtime error	2 ms	604 KB	Execution killed with signal 11
54	Runtime error	2 ms	604 KB	Execution killed with signal 11
55	Runtime error	2 ms	604 KB	Execution killed with signal 11
56	Runtime error	2 ms	600 KB	Execution killed with signal 11
57	Runtime error	2 ms	604 KB	Execution killed with signal 11
58	Runtime error	2 ms	520 KB	Execution killed with signal 11
59	Runtime error	2 ms	604 KB	Execution killed with signal 11
60	Runtime error	2 ms	604 KB	Execution killed with signal 11
61	Runtime error	2 ms	604 KB	Execution killed with signal 11
62	Runtime error	2 ms	604 KB	Execution killed with signal 11
63	Runtime error	2 ms	604 KB	Execution killed with signal 11
64	Runtime error	2 ms	604 KB	Execution killed with signal 11
65	Runtime error	2 ms	604 KB	Execution killed with signal 11
66	Runtime error	2 ms	604 KB	Execution killed with signal 11
67	Runtime error	2 ms	604 KB	Execution killed with signal 11
68	Runtime error	2 ms	604 KB	Execution killed with signal 11
69	Runtime error	2 ms	604 KB	Execution killed with signal 11
70	Runtime error	2 ms	604 KB	Execution killed with signal 11
71	Runtime error	2 ms	604 KB	Execution killed with signal 11
72	Runtime error	2 ms	604 KB	Execution killed with signal 11
73	Runtime error	2 ms	604 KB	Execution killed with signal 11
74	Runtime error	2 ms	604 KB	Execution killed with signal 11
75	Runtime error	2 ms	532 KB	Execution killed with signal 11
76	Runtime error	2 ms	604 KB	Execution killed with signal 11
77	Runtime error	2 ms	604 KB	Execution killed with signal 11
78	Runtime error	2 ms	600 KB	Execution killed with signal 11
79	Runtime error	2 ms	604 KB	Execution killed with signal 11
80	Runtime error	3 ms	524 KB	Execution killed with signal 11
81	Runtime error	2 ms	604 KB	Execution killed with signal 11
82	Runtime error	2 ms	604 KB	Execution killed with signal 11
83	Runtime error	2 ms	604 KB	Execution killed with signal 11
84	Runtime error	2 ms	604 KB	Execution killed with signal 11
85	Runtime error	2 ms	524 KB	Execution killed with signal 11
86	Runtime error	2 ms	604 KB	Execution killed with signal 11
87	Runtime error	2 ms	604 KB	Execution killed with signal 11
88	Runtime error	2 ms	604 KB	Execution killed with signal 11
89	Runtime error	2 ms	604 KB	Execution killed with signal 11
90	Runtime error	2 ms	604 KB	Execution killed with signal 11
91	Runtime error	2 ms	600 KB	Execution killed with signal 11
92	Runtime error	2 ms	524 KB	Execution killed with signal 11