oj.uz

답안 #583518

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
583518 2022-06-25T13:30:08 Z Trent Mecho (IOI09_mecho) C++17
15 / 100
 190 ms 6988 KB 
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"

using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define open(g) string _name_ = g; freopen((_name_ + ".in").c_str(), "r", stdin); freopen((_name_ + ".out").c_str(), "w", stdout)
#define printArr(a, len) for(int asdf = 0; asdf < (len); ++asdf) cout << (a)[asdf] << ' '; cout << '\n';
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define forR(i, x) for(int i = 0; i < x; ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(i) i.begin(), i.end()
#define pii pair<int, int>
#define vi vector<int>
#define si set<int>
#define usi unordered_set<int>
#define mii map<int, int>
#define umii unordered_map<int, int>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

const int MN = 810, INF = 1e9 + 10;
struct coord{int r, c;};
struct bear{int r, c, sl;};
bool vis[MN][MN];
int bee[MN][MN], ber[MN][MN]; // minimum # of minutes needed to end here
char grid[MN][MN];
int dir[4][2] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
int n, s;
int mr, mc;

bool ib(int r, int c){return 0 <= r && r < n && 0 <= c && c < n;}
bool iv(int r, int c){return ib(r, c) && grid[r][c] != 'T';}

// t = number of minutes bear eats
bool pos(int t){
    deque<bear> bfs = {{mr, mc, s}};
    forR(a, MN) forR(b, MN) vis[a][b] = false;
    ber[mr][mc] = t;
    while(!bfs.empty()){
        auto [r, c, sl] = bfs.front();
        bfs.pop_front();
        if(grid[r][c] == 'D') return true;
        for(auto [rc, cc] : dir){
            auto [nr, nc] = pii{r+rc, c+cc};
            int dis = ber[r][c] + (sl == 0);
            if(iv(nr, nc) && !vis[nr][nc] && dis < bee[nr][nc]){
                ber[nr][nc] = dis;
                vis[nr][nc] = true;
                if(sl == 0) bfs.push_back({nr, nc, s});
                else bfs.push_front({nr, nc, sl-1});
            }
        }
    }
    return false;
}

signed main() {
    cin >> n >> s;
    deque<coord> bfs;
    forR(r, n) forR(c, n){
        cin >> grid[r][c];
        if(grid[r][c] == 'H') {
            bfs.push_back({r, c});
            vis[r][c] = true;
        } else if(grid[r][c] == 'M'){
            mr=r, mc=c;
        }
    }
    while(!bfs.empty()){
        auto [r, c] = bfs.front();
        bfs.pop_front();
        for(auto [cr, cc] : dir){
            auto [nr, nc] = pii {r + cr, c + cc};
            if(iv(nr, nc) && grid[nr][nc] != 'D' && !vis[nr][nc]){
                vis[nr][nc] = true;
                bee[nr][nc] = bee[r][c] + 1;
                bfs.push_back({nr, nc});
            }
        }
    }
    forR(r, MN) forR(c, MN) if(!vis[r][c]) bee[r][c] = INF;
    if(!pos(0)) cout << "-1\n";
    else {
        int lo=0, hi=MN * MN;
        while(hi - lo > 1){
            int mid = (lo + hi) / 2;
            if(pos(mid)) lo = mid;
            else hi = mid;
        }
        cout << lo << '\n';
    }
}

Subtask #1
15.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 3412 KB Output isn't correct
2 Incorrect 2 ms 3540 KB Output isn't correct
3 Incorrect 3 ms 3540 KB Output isn't correct
4 Incorrect 2 ms 3540 KB Output isn't correct
5 Correct 3 ms 3540 KB Output is correct
6 Incorrect 2 ms 3540 KB Output isn't correct
7 Incorrect 130 ms 5820 KB Output isn't correct
8 Incorrect 3 ms 3540 KB Output isn't correct
9 Correct 3 ms 3540 KB Output is correct
10 Incorrect 2 ms 3540 KB Output isn't correct
11 Correct 3 ms 3540 KB Output is correct
12 Incorrect 3 ms 3540 KB Output isn't correct
13 Incorrect 3 ms 3540 KB Output isn't correct
14 Correct 2 ms 3668 KB Output is correct
15 Incorrect 3 ms 3540 KB Output isn't correct
16 Correct 3 ms 3540 KB Output is correct
17 Incorrect 3 ms 3540 KB Output isn't correct
18 Correct 3 ms 3540 KB Output is correct
19 Incorrect 3 ms 3540 KB Output isn't correct
20 Correct 3 ms 3540 KB Output is correct
21 Incorrect 3 ms 3540 KB Output isn't correct
22 Correct 3 ms 3540 KB Output is correct
23 Incorrect 3 ms 3540 KB Output isn't correct
24 Correct 3 ms 3540 KB Output is correct
25 Incorrect 3 ms 3540 KB Output isn't correct
26 Correct 3 ms 3540 KB Output is correct
27 Incorrect 3 ms 3540 KB Output isn't correct
28 Correct 3 ms 3540 KB Output is correct
29 Incorrect 3 ms 3540 KB Output isn't correct
30 Correct 3 ms 3540 KB Output is correct
31 Incorrect 3 ms 3540 KB Output isn't correct
32 Correct 3 ms 3540 KB Output is correct
33 Incorrect 10 ms 3768 KB Output isn't correct
34 Correct 13 ms 3796 KB Output is correct
35 Incorrect 42 ms 4896 KB Output isn't correct
36 Incorrect 16 ms 3796 KB Output isn't correct
37 Correct 14 ms 3796 KB Output is correct
38 Incorrect 49 ms 5160 KB Output isn't correct
39 Incorrect 17 ms 3796 KB Output isn't correct
40 Correct 15 ms 3916 KB Output is correct
41 Incorrect 56 ms 5400 KB Output isn't correct
42 Incorrect 19 ms 3924 KB Output isn't correct
43 Correct 20 ms 3924 KB Output is correct
44 Incorrect 75 ms 5608 KB Output isn't correct
45 Incorrect 23 ms 3956 KB Output isn't correct
46 Correct 24 ms 3924 KB Output is correct
47 Incorrect 86 ms 5828 KB Output isn't correct
48 Incorrect 27 ms 3876 KB Output isn't correct
49 Correct 25 ms 3976 KB Output is correct
50 Incorrect 102 ms 6092 KB Output isn't correct
51 Incorrect 34 ms 4052 KB Output isn't correct
52 Correct 32 ms 4056 KB Output is correct
53 Incorrect 123 ms 6284 KB Output isn't correct
54 Incorrect 33 ms 4044 KB Output isn't correct
55 Correct 33 ms 4048 KB Output is correct
56 Incorrect 50 ms 6388 KB Output isn't correct
57 Incorrect 45 ms 4044 KB Output isn't correct
58 Correct 41 ms 4124 KB Output is correct
59 Incorrect 55 ms 6652 KB Output isn't correct
60 Incorrect 42 ms 4132 KB Output isn't correct
61 Correct 43 ms 4060 KB Output is correct
62 Incorrect 69 ms 6884 KB Output isn't correct
63 Incorrect 182 ms 6672 KB Output isn't correct
64 Correct 169 ms 6608 KB Output is correct
65 Incorrect 184 ms 6684 KB Output isn't correct
66 Incorrect 157 ms 6676 KB Output isn't correct
67 Incorrect 190 ms 6604 KB Output isn't correct
68 Incorrect 76 ms 6604 KB Output isn't correct
69 Correct 77 ms 6688 KB Output is correct
70 Incorrect 75 ms 6692 KB Output isn't correct
71 Incorrect 69 ms 6604 KB Output isn't correct
72 Incorrect 59 ms 5288 KB Output isn't correct
73 Incorrect 73 ms 6936 KB Output isn't correct
74 Incorrect 123 ms 6916 KB Output isn't correct
75 Incorrect 126 ms 6940 KB Output isn't correct
76 Incorrect 107 ms 6940 KB Output isn't correct
77 Incorrect 112 ms 6944 KB Output isn't correct
78 Correct 62 ms 5540 KB Output is correct
79 Incorrect 97 ms 6988 KB Output isn't correct
80 Incorrect 100 ms 5624 KB Output isn't correct
81 Incorrect 102 ms 5480 KB Output isn't correct
82 Incorrect 99 ms 5668 KB Output isn't correct
83 Incorrect 66 ms 5452 KB Output isn't correct
84 Incorrect 119 ms 5336 KB Output isn't correct
85 Incorrect 113 ms 5588 KB Output isn't correct
86 Incorrect 116 ms 5564 KB Output isn't correct
87 Incorrect 122 ms 5536 KB Output isn't correct
88 Incorrect 77 ms 5452 KB Output isn't correct
89 Incorrect 138 ms 5584 KB Output isn't correct
90 Incorrect 134 ms 5644 KB Output isn't correct
91 Incorrect 133 ms 5812 KB Output isn't correct
92 Incorrect 130 ms 5584 KB Output isn't correct