oj.uz

답안 #470809

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
470809 2021-09-05T19:25:37 Z Yazan_Alattar Mecho (IOI09_mecho) C++14
76 / 100
 214 ms 8600 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;
        if(dist[st.F][st.S] - 1 >= d[st.F][st.S] - s) q.pop();
        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
76.0 / 100.0

# 결과 실행 시간 메모리 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 4260 KB Output is correct
5 Correct 5 ms 4308 KB Output is correct
6 Correct 4 ms 4300 KB Output is correct
7 Correct 137 ms 8260 KB Output is correct
8 Correct 4 ms 4300 KB Output is correct
9 Correct 4 ms 4300 KB Output is correct
10 Correct 4 ms 4300 KB Output is correct
11 Correct 4 ms 4300 KB Output is correct
12 Correct 4 ms 4556 KB Output is correct
13 Correct 4 ms 4428 KB Output is correct
14 Correct 6 ms 4556 KB Output is correct
15 Correct 4 ms 4300 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 4428 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 4556 KB Output is correct
26 Correct 5 ms 4556 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 4616 KB Output is correct
30 Correct 5 ms 4624 KB Output is correct
31 Correct 5 ms 4556 KB Output is correct
32 Correct 5 ms 4556 KB Output is correct
33 Incorrect 21 ms 5932 KB Output isn't correct
34 Incorrect 25 ms 5976 KB Output isn't correct
35 Correct 34 ms 5984 KB Output is correct
36 Incorrect 27 ms 6244 KB Output isn't correct
37 Incorrect 33 ms 6236 KB Output isn't correct
38 Correct 45 ms 6232 KB Output is correct
39 Incorrect 33 ms 6480 KB Output isn't correct
40 Incorrect 43 ms 6464 KB Output isn't correct
41 Correct 55 ms 6476 KB Output is correct
42 Incorrect 41 ms 6688 KB Output isn't correct
43 Incorrect 50 ms 6724 KB Output isn't correct
44 Correct 67 ms 6724 KB Output is correct
45 Incorrect 47 ms 6964 KB Output isn't correct
46 Incorrect 62 ms 6932 KB Output isn't correct
47 Correct 83 ms 6972 KB Output is correct
48 Incorrect 56 ms 7100 KB Output isn't correct
49 Incorrect 75 ms 7108 KB Output isn't correct
50 Correct 94 ms 7228 KB Output is correct
51 Incorrect 74 ms 7468 KB Output isn't correct
52 Incorrect 107 ms 7452 KB Output isn't correct
53 Correct 120 ms 7400 KB Output is correct
54 Incorrect 73 ms 7700 KB Output isn't correct
55 Incorrect 100 ms 7620 KB Output isn't correct
56 Correct 140 ms 7620 KB Output is correct
57 Incorrect 87 ms 8056 KB Output isn't correct
58 Incorrect 117 ms 7960 KB Output isn't correct
59 Correct 155 ms 7956 KB Output is correct
60 Incorrect 97 ms 8160 KB Output isn't correct
61 Incorrect 135 ms 8196 KB Output isn't correct
62 Correct 174 ms 8200 KB Output is correct
63 Correct 175 ms 8116 KB Output is correct
64 Correct 214 ms 8200 KB Output is correct
65 Correct 211 ms 8124 KB Output is correct
66 Correct 159 ms 8132 KB Output is correct
67 Correct 168 ms 8196 KB Output is correct
68 Correct 91 ms 8192 KB Output is correct
69 Correct 81 ms 8216 KB Output is correct
70 Correct 76 ms 8168 KB Output is correct
71 Correct 78 ms 8228 KB Output is correct
72 Correct 70 ms 8148 KB Output is correct
73 Correct 79 ms 8568 KB Output is correct
74 Correct 104 ms 8600 KB Output is correct
75 Correct 113 ms 8516 KB Output is correct
76 Correct 105 ms 8388 KB Output is correct
77 Correct 106 ms 8388 KB Output is correct
78 Correct 124 ms 8404 KB Output is correct
79 Correct 91 ms 8388 KB Output is correct
80 Correct 99 ms 8464 KB Output is correct
81 Correct 130 ms 8424 KB Output is correct
82 Correct 99 ms 8516 KB Output is correct
83 Correct 126 ms 8332 KB Output is correct
84 Correct 111 ms 8448 KB Output is correct
85 Correct 115 ms 8344 KB Output is correct
86 Correct 117 ms 8400 KB Output is correct
87 Correct 115 ms 8388 KB Output is correct
88 Correct 129 ms 8260 KB Output is correct
89 Correct 129 ms 8268 KB Output is correct
90 Correct 125 ms 8260 KB Output is correct
91 Correct 175 ms 8348 KB Output is correct
92 Correct 127 ms 8332 KB Output is correct