oj.uz

Submission #977333

# Submission time Handle Problem Language Result Execution time Memory
977333 2024-05-07T18:30:59 Z farica Mecho (IOI09_mecho) C++14
2 / 100
 391 ms 65540 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MAX_N = 4e5 + 5;
const int MOD = 998244353;

void solve() {
    int n, s;
    cin >> n >> s;
    string grid[n];
    int sx=0, sy=0;
    vector<vector<int>>depth(n, vector<int>(n, -1));
    queue<pair<int,int>>q;
    for(int i=0; i<n; ++i) {
        cin >> grid[i];
        for(int j=0; j<n; ++j) {
            if(grid[i][j] == 'M') {
                sx=i;
                sy=j;
            }
            else if(grid[i][j] == 'H') {
                q.push({i, j});
                depth[i][j] = 0;
            }
        }
    }
    while(!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        if(x && grid[x-1][y] != 'T' && depth[x-1][y] == -1) {
            depth[x-1][y] = depth[x][y] + 1;
            q.push({x-1, y});
        }
        if(y && grid[x][y-1] != 'T' && depth[x][y-1] == -1) {
            depth[x][y-1] = depth[x][y] + 1;
            q.push({x, y-1});
        }
        if(x+1<n && grid[x+1][y] != 'T' && depth[x+1][y] == -1) {
            depth[x+1][y] = depth[x][y] + 1;
            q.push({x+1, y});
        }
        if(y+1<n && grid[x][y+1] != 'T' && depth[x][y+1] == -1) {
            depth[x][y+1] = depth[x][y] + 1;
            q.push({x, y+1});
        }
    }
    priority_queue<pair<pair<int,int>, pair<int,int>>>pq;
    pq.push({{depth[sx][sy], 0}, {sx, sy}});
    while(!pq.empty()) {
        int t = pq.top().first.first, visited = pq.top().first.second, x = pq.top().second.first, y = pq.top().second.second;
        pq.pop();
        if(grid[x][y] == 'D') {
            cout << t << endl;
            return;
        }
        int new_t, cost = (visited+1)/s + ((visited+1) % s > 0 ? 1 : 0);
        if(x && grid[x-1][y] != 'T') {
            new_t = min(t, depth[x-1][y] - cost);
            if(new_t >= 0) pq.push({{new_t, visited + 1}, {x-1, y}});
        }
        if(y && grid[x][y-1] != 'T') {
            new_t = min(t, depth[x][y-1] - cost);
            if(new_t >= 0) pq.push({{new_t, visited + 1}, {x, y-1}});
        }
        if(x+1<n && grid[x+1][y] != 'T') {
            new_t = min(t, depth[x+1][y] - cost);
            if(new_t >= 0) pq.push({{new_t, visited + 1}, {x+1, y}});
        }
        if(y+1<n && grid[x][y+1] != 'T') {
            new_t = min(t, depth[x][y+1] - cost);
            if(new_t >= 0) pq.push({{new_t, visited + 1}, {x, y+1}});
        }
    }
    cout << -1 << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t=1;
    while(t--) solve();

    return 0;
}

Subtask #1
2.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Correct 2 ms 348 KB Output is correct
6 Runtime error 209 ms 65536 KB Execution killed with signal 9
7 Runtime error 179 ms 65536 KB Execution killed with signal 9
8 Incorrect 1 ms 344 KB Output isn't correct
9 Correct 0 ms 376 KB Output is correct
10 Correct 6 ms 2508 KB Output is correct
11 Correct 39 ms 16992 KB Output is correct
12 Incorrect 1 ms 348 KB Output isn't correct
13 Runtime error 160 ms 65536 KB Execution killed with signal 9
14 Runtime error 146 ms 65536 KB Execution killed with signal 9
15 Incorrect 1 ms 348 KB Output isn't correct
16 Runtime error 227 ms 65536 KB Execution killed with signal 9
17 Incorrect 1 ms 344 KB Output isn't correct
18 Runtime error 213 ms 65536 KB Execution killed with signal 9
19 Incorrect 0 ms 348 KB Output isn't correct
20 Runtime error 219 ms 65536 KB Execution killed with signal 9
21 Incorrect 0 ms 344 KB Output isn't correct
22 Runtime error 208 ms 65536 KB Execution killed with signal 9
23 Incorrect 1 ms 344 KB Output isn't correct
24 Runtime error 208 ms 65536 KB Execution killed with signal 9
25 Incorrect 1 ms 604 KB Output isn't correct
26 Runtime error 209 ms 65536 KB Execution killed with signal 9
27 Incorrect 1 ms 604 KB Output isn't correct
28 Runtime error 194 ms 65536 KB Execution killed with signal 9
29 Incorrect 1 ms 600 KB Output isn't correct
30 Runtime error 205 ms 65536 KB Execution killed with signal 9
31 Incorrect 1 ms 604 KB Output isn't correct
32 Runtime error 206 ms 65536 KB Execution killed with signal 9
33 Incorrect 12 ms 3788 KB Output isn't correct
34 Runtime error 194 ms 65536 KB Execution killed with signal 9
35 Runtime error 293 ms 65536 KB Execution killed with signal 9
36 Incorrect 15 ms 7120 KB Output isn't correct
37 Runtime error 194 ms 65536 KB Execution killed with signal 9
38 Runtime error 299 ms 65536 KB Execution killed with signal 9
39 Incorrect 19 ms 8392 KB Output isn't correct
40 Runtime error 187 ms 65536 KB Execution killed with signal 9
41 Runtime error 296 ms 65536 KB Execution killed with signal 9
42 Incorrect 26 ms 7892 KB Output isn't correct
43 Runtime error 189 ms 65536 KB Execution killed with signal 9
44 Runtime error 293 ms 65536 KB Execution killed with signal 9
45 Incorrect 32 ms 12736 KB Output isn't correct
46 Runtime error 186 ms 65536 KB Execution killed with signal 9
47 Runtime error 293 ms 65536 KB Execution killed with signal 9
48 Incorrect 33 ms 12780 KB Output isn't correct
49 Runtime error 189 ms 65536 KB Execution killed with signal 9
50 Runtime error 301 ms 65536 KB Execution killed with signal 9
51 Incorrect 39 ms 12800 KB Output isn't correct
52 Runtime error 184 ms 65536 KB Execution killed with signal 9
53 Runtime error 293 ms 65536 KB Execution killed with signal 9
54 Incorrect 46 ms 14580 KB Output isn't correct
55 Runtime error 187 ms 65536 KB Execution killed with signal 9
56 Runtime error 313 ms 65536 KB Execution killed with signal 9
57 Incorrect 51 ms 22260 KB Output isn't correct
58 Runtime error 185 ms 65536 KB Execution killed with signal 9
59 Runtime error 298 ms 65536 KB Execution killed with signal 9
60 Incorrect 59 ms 23228 KB Output isn't correct
61 Runtime error 184 ms 65536 KB Execution killed with signal 9
62 Runtime error 299 ms 65536 KB Execution killed with signal 9
63 Runtime error 284 ms 65536 KB Execution killed with signal 9
64 Runtime error 326 ms 65536 KB Execution killed with signal 9
65 Runtime error 366 ms 65536 KB Execution killed with signal 9
66 Runtime error 347 ms 65536 KB Execution killed with signal 9
67 Runtime error 284 ms 65536 KB Execution killed with signal 9
68 Runtime error 353 ms 65536 KB Execution killed with signal 9
69 Runtime error 334 ms 65536 KB Execution killed with signal 9
70 Runtime error 391 ms 65536 KB Execution killed with signal 9
71 Runtime error 356 ms 65536 KB Execution killed with signal 9
72 Runtime error 321 ms 65536 KB Execution killed with signal 9
73 Runtime error 176 ms 65536 KB Execution killed with signal 9
74 Runtime error 200 ms 65536 KB Execution killed with signal 9
75 Runtime error 202 ms 65536 KB Execution killed with signal 9
76 Runtime error 158 ms 65536 KB Execution killed with signal 9
77 Runtime error 218 ms 65536 KB Execution killed with signal 9
78 Runtime error 227 ms 65536 KB Execution killed with signal 9
79 Runtime error 198 ms 65536 KB Execution killed with signal 9
80 Runtime error 226 ms 65536 KB Execution killed with signal 9
81 Runtime error 234 ms 65536 KB Execution killed with signal 9
82 Runtime error 222 ms 65536 KB Execution killed with signal 9
83 Runtime error 155 ms 65536 KB Execution killed with signal 9
84 Runtime error 144 ms 65540 KB Execution killed with signal 9
85 Runtime error 221 ms 65536 KB Execution killed with signal 9
86 Runtime error 153 ms 65536 KB Execution killed with signal 9
87 Runtime error 145 ms 65536 KB Execution killed with signal 9
88 Runtime error 221 ms 65536 KB Execution killed with signal 9
89 Runtime error 201 ms 65536 KB Execution killed with signal 9
90 Runtime error 215 ms 65536 KB Execution killed with signal 9
91 Runtime error 214 ms 65536 KB Execution killed with signal 9
92 Runtime error 218 ms 65536 KB Execution killed with signal 9