oj.uz

Submission #470808

# Submission time Handle Problem Language Result Execution time Memory
470808 2021-09-05T19:20:16 Z Yazan_Alattar Mecho (IOI09_mecho) C++14
60 / 100
 204 ms 8516 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 1007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

queue < pair <int,int> > q;
pair <int,int> st, en;
int n, s, d[M][M], dist[M][M];
char a[M][M];

int main()
{
//    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> s;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            cin >> a[i][j];
            if(a[i][j] == 'H') q.push({i, j}), d[i][j] = s;
            if(a[i][j] == 'D') en = {i, j};
            if(a[i][j] == 'M') st = {i, j};
        }
    }
    while(!q.empty()){
        int x = q.front().S;
        int y = q.front().F;
        q.pop();
        for(int i = 0; i < 4; ++i){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(a[ny][nx] == 'H' || a[ny][nx] == 'T' || a[ny][nx] == 'D' || d[ny][nx] || ny < 1 || nx < 1 || ny > n || nx > n) continue;
            d[ny][nx] = d[y][x] + s;
            q.push({ny, nx});
        }
    }
    d[en.F][en.S] = 1e9;
    int l = 0, r = 1e4;
    while(l < r){
        memset(dist, 0, sizeof dist);
        int mid = (l + r) / 2;
        q.push(st);
        dist[st.F][st.S] = mid * s + 1;
        while(!q.empty()){
            int x = q.front().S;
            int y = q.front().F;
            q.pop();
            for(int i = 0; i < 4; ++i){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(a[ny][nx] == 'H' || a[ny][nx] == 'T' || dist[ny][nx] || dist[y][x] >= d[ny][nx] - s || ny > n || nx > n || ny < 1 || nx < 1) continue;
                dist[ny][nx] = dist[y][x] + 1;
                q.push({ny, nx});
            }
        }
        if(dist[en.F][en.S]) l = mid + 1;
        else r = mid;
    }
    cout << l - 1 << endl;
    return 0;
}
// Don't forget special cases. (n = 1?)
// Look for the constraints. (Runtime array? overflow?)

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4300 KB Output is correct
2 Correct 4 ms 4300 KB Output is correct
3 Correct 4 ms 4300 KB Output is correct
4 Correct 4 ms 4300 KB Output is correct
5 Correct 4 ms 4300 KB Output is correct
6 Correct 4 ms 4300 KB Output is correct
7 Correct 138 ms 8308 KB Output is correct
8 Correct 5 ms 4348 KB Output is correct
9 Correct 4 ms 4300 KB Output is correct
10 Correct 4 ms 4328 KB Output is correct
11 Correct 5 ms 4300 KB Output is correct
12 Incorrect 4 ms 4556 KB Output isn't correct
13 Incorrect 5 ms 4428 KB Output isn't correct
14 Correct 5 ms 4568 KB Output is correct
15 Correct 4 ms 4368 KB Output is correct
16 Correct 4 ms 4300 KB Output is correct
17 Correct 4 ms 4300 KB Output is correct
18 Correct 4 ms 4300 KB Output is correct
19 Correct 4 ms 4300 KB Output is correct
20 Correct 4 ms 4300 KB Output is correct
21 Correct 4 ms 4428 KB Output is correct
22 Correct 4 ms 4428 KB Output is correct
23 Correct 4 ms 4428 KB Output is correct
24 Correct 4 ms 4428 KB Output is correct
25 Correct 5 ms 4568 KB Output is correct
26 Correct 5 ms 4684 KB Output is correct
27 Correct 5 ms 4556 KB Output is correct
28 Correct 5 ms 4556 KB Output is correct
29 Correct 5 ms 4556 KB Output is correct
30 Correct 5 ms 4556 KB Output is correct
31 Correct 5 ms 4556 KB Output is correct
32 Correct 4 ms 4556 KB Output is correct
33 Incorrect 20 ms 6004 KB Output isn't correct
34 Incorrect 24 ms 5924 KB Output isn't correct
35 Correct 35 ms 5932 KB Output is correct
36 Incorrect 27 ms 6200 KB Output isn't correct
37 Incorrect 31 ms 6220 KB Output isn't correct
38 Correct 43 ms 6220 KB Output is correct
39 Incorrect 31 ms 6500 KB Output isn't correct
40 Incorrect 44 ms 6484 KB Output isn't correct
41 Correct 66 ms 6428 KB Output is correct
42 Incorrect 39 ms 6732 KB Output isn't correct
43 Incorrect 49 ms 6724 KB Output isn't correct
44 Correct 68 ms 6748 KB Output is correct
45 Incorrect 46 ms 6980 KB Output isn't correct
46 Incorrect 60 ms 6960 KB Output isn't correct
47 Correct 94 ms 6856 KB Output is correct
48 Incorrect 53 ms 7108 KB Output isn't correct
49 Incorrect 74 ms 7208 KB Output isn't correct
50 Correct 93 ms 7220 KB Output is correct
51 Incorrect 63 ms 7356 KB Output isn't correct
52 Incorrect 85 ms 7440 KB Output isn't correct
53 Correct 113 ms 7412 KB Output is correct
54 Incorrect 73 ms 7672 KB Output isn't correct
55 Incorrect 99 ms 7644 KB Output isn't correct
56 Correct 138 ms 7708 KB Output is correct
57 Incorrect 86 ms 7960 KB Output isn't correct
58 Incorrect 117 ms 7968 KB Output isn't correct
59 Correct 154 ms 7940 KB Output is correct
60 Incorrect 93 ms 8112 KB Output isn't correct
61 Incorrect 126 ms 8200 KB Output isn't correct
62 Correct 182 ms 8156 KB Output is correct
63 Correct 152 ms 8188 KB Output is correct
64 Correct 204 ms 8132 KB Output is correct
65 Correct 201 ms 8196 KB Output is correct
66 Correct 161 ms 8204 KB Output is correct
67 Correct 157 ms 8136 KB Output is correct
68 Correct 86 ms 8220 KB Output is correct
69 Correct 78 ms 8132 KB Output is correct
70 Correct 73 ms 8232 KB Output is correct
71 Correct 69 ms 8196 KB Output is correct
72 Incorrect 65 ms 8132 KB Output isn't correct
73 Incorrect 73 ms 8516 KB Output isn't correct
74 Correct 95 ms 8472 KB Output is correct
75 Correct 108 ms 8380 KB Output is correct
76 Correct 102 ms 8480 KB Output is correct
77 Correct 106 ms 8424 KB Output is correct
78 Correct 125 ms 8440 KB Output is correct
79 Correct 89 ms 8424 KB Output is correct
80 Correct 97 ms 8440 KB Output is correct
81 Correct 114 ms 8460 KB Output is correct
82 Correct 94 ms 8388 KB Output is correct
83 Correct 130 ms 8404 KB Output is correct
84 Correct 108 ms 8288 KB Output is correct
85 Correct 109 ms 8388 KB Output is correct
86 Correct 116 ms 8404 KB Output is correct
87 Correct 116 ms 8336 KB Output is correct
88 Correct 130 ms 8352 KB Output is correct
89 Correct 122 ms 8232 KB Output is correct
90 Correct 125 ms 8292 KB Output is correct
91 Correct 128 ms 8260 KB Output is correct
92 Correct 122 ms 8256 KB Output is correct