답안 #965426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
965426	2024-04-18T13:57:17 Z	Alihan_8	Mecho (IOI09_mecho)	C++17	63 / 100	160 ms	12440 KB

mecho

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const int inf = 1e9;

int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k; cin >> n >> k;
    vector <string> a(n);
    for ( auto &u: a ) cin >> u;
    ar <int,2> s, e;
    vector <vector<int>> bee(n, vector <int> (n, inf));
    queue <ar<int,2>> q;
    for ( int i = 0; i < n; i++ ){
        for ( int j = 0; j < n; j++ ){
            if ( a[i][j] == 'M' ){
                s = {i, j};
            }
            if ( a[i][j] == 'D' ){
                e = {i, j};
            }
            if ( a[i][j] == 'H' ){
                q.push({i, j});
                bee[i][j] = 0;
            }
        }
    }
    auto ok = [&](int u, int v){
        return u >= 0 && v >= 0 && u < n && v < n;
    };
    while ( !q.empty() ){
        auto [u, v] = q.front();
        q.pop();
        for ( int i = 0; i < 4; i++ ){
            int x = dx[i] + u, y = dy[i] + v;
            if ( ok(x, y) && a[x][y] != 'T' && a[x][y] != 'D' ){
                if ( chmin(bee[x][y], bee[u][v] + 1) ){
                    q.push({x, y});
                }
            }
        }
    }
    auto valid = [&](int t){
        if ( bee[s[0]][s[1]] <= t ){
            return false;
        }
        vector <vector<int>> dp(n, vector <int> (n, inf));
        dp[s[0]][s[1]] = t + 1;
        deque <ar<int,3>> q;
        q.pb({s[0], s[1], k});
        while ( !q.empty() ){
            auto [u, v, r] = q.front();
            q.pop_front();
            for ( int i = 0; i < 4; i++ ){
                int x = dx[i] + u, y = dy[i] + v;
                if ( !ok(x, y) || a[x][y] == 'T' ){
                    continue;
                }
                if ( r == 0 ){
                    if ( chmin(dp[x][y], dp[u][v] + 1) ){
                        q.pb({x, y, k});
                    }
                } else if ( r == 1 ){
                    if ( bee[x][y] > dp[u][v] ){
                        if ( chmin(dp[x][y], dp[u][v]) ){
                            q.push_front({x, y, r - 1});
                        }
                    }
                } else{
                    if ( bee[x][y] >= dp[u][v] ){
                        if ( chmin(dp[x][y], dp[u][v]) ){
                            q.push_front({x, y, r - 1});
                        }
                    }
                }
            }
        }
        for ( int i = 0; i < n; i++ ){
            for ( int j = 0; j < n; j++ ){

            }
        }
        return dp[e[0]][e[1]] != inf;
    };
    int l = 0, r = inf;
    while ( l + 1 < r ){
        int md = (l + r) >> 1;
        if ( valid(md) ){
            l = md;
        } else r = md;
    }
    cout << (valid(l) ? l : -1);

    cout << '\n';
}

Subtask #1

63.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Incorrect	0 ms	348 KB	Output isn't correct
3	Correct	1 ms	348 KB	Output is correct
4	Incorrect	0 ms	348 KB	Output isn't correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Incorrect	116 ms	11296 KB	Output isn't correct
8	Incorrect	0 ms	344 KB	Output isn't correct
9	Correct	1 ms	348 KB	Output is correct
10	Incorrect	0 ms	348 KB	Output isn't correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	600 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct
31	Correct	1 ms	348 KB	Output is correct
32	Correct	1 ms	348 KB	Output is correct
33	Correct	7 ms	2556 KB	Output is correct
34	Correct	6 ms	2552 KB	Output is correct
35	Correct	25 ms	2768 KB	Output is correct
36	Correct	6 ms	3160 KB	Output is correct
37	Correct	6 ms	3164 KB	Output is correct
38	Correct	33 ms	3464 KB	Output is correct
39	Correct	9 ms	4016 KB	Output is correct
40	Correct	8 ms	3856 KB	Output is correct
41	Correct	41 ms	4184 KB	Output is correct
42	Correct	9 ms	4676 KB	Output is correct
43	Correct	7 ms	4676 KB	Output is correct
44	Correct	54 ms	5224 KB	Output is correct
45	Correct	13 ms	5564 KB	Output is correct
46	Correct	14 ms	5608 KB	Output is correct
47	Correct	67 ms	6216 KB	Output is correct
48	Correct	18 ms	6608 KB	Output is correct
49	Correct	17 ms	6588 KB	Output is correct
50	Correct	101 ms	7256 KB	Output is correct
51	Correct	20 ms	7608 KB	Output is correct
52	Correct	21 ms	7616 KB	Output is correct
53	Correct	94 ms	8404 KB	Output is correct
54	Correct	28 ms	8812 KB	Output is correct
55	Correct	29 ms	8748 KB	Output is correct
56	Correct	110 ms	9676 KB	Output is correct
57	Correct	24 ms	10004 KB	Output is correct
58	Correct	22 ms	9984 KB	Output is correct
59	Correct	136 ms	11040 KB	Output is correct
60	Correct	26 ms	11292 KB	Output is correct
61	Correct	33 ms	11420 KB	Output is correct
62	Correct	151 ms	12440 KB	Output is correct
63	Incorrect	148 ms	11240 KB	Output isn't correct
64	Correct	149 ms	11256 KB	Output is correct
65	Incorrect	160 ms	11252 KB	Output isn't correct
66	Incorrect	143 ms	11260 KB	Output isn't correct
67	Incorrect	156 ms	11268 KB	Output isn't correct
68	Incorrect	52 ms	11328 KB	Output isn't correct
69	Correct	63 ms	11304 KB	Output is correct
70	Incorrect	38 ms	11260 KB	Output isn't correct
71	Incorrect	43 ms	11284 KB	Output isn't correct
72	Correct	31 ms	11268 KB	Output is correct
73	Correct	37 ms	11088 KB	Output is correct
74	Incorrect	94 ms	11392 KB	Output isn't correct
75	Incorrect	92 ms	11240 KB	Output isn't correct
76	Incorrect	83 ms	11232 KB	Output isn't correct
77	Incorrect	98 ms	11088 KB	Output isn't correct
78	Correct	90 ms	11312 KB	Output is correct
79	Incorrect	78 ms	11456 KB	Output isn't correct
80	Incorrect	90 ms	11272 KB	Output isn't correct
81	Incorrect	92 ms	11296 KB	Output isn't correct
82	Incorrect	87 ms	11260 KB	Output isn't correct
83	Incorrect	108 ms	11292 KB	Output isn't correct
84	Incorrect	119 ms	11752 KB	Output isn't correct
85	Incorrect	93 ms	11308 KB	Output isn't correct
86	Incorrect	125 ms	11296 KB	Output isn't correct
87	Incorrect	100 ms	11132 KB	Output isn't correct
88	Incorrect	105 ms	11344 KB	Output isn't correct
89	Correct	123 ms	11936 KB	Output is correct
90	Incorrect	111 ms	11308 KB	Output isn't correct
91	Incorrect	111 ms	11356 KB	Output isn't correct
92	Incorrect	100 ms	11228 KB	Output isn't correct