oj.uz

답안 #650099

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
650099 2022-10-12T11:56:26 Z mychecksedad Mecho (IOI09_mecho) C++17
24 / 100
 447 ms 65536 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;



int n, S, ax, ay, bx, by, dist[1000][1000], d[1000][1000], arr[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
string s[N];
bool vis[1000][1000];
void solve(){
    cin >> n >> S;
    queue<array<int, 2>> q, q1;
    for(int i = 0; i < n; ++i){
        cin >> s[i];
        for(int j = 0; j < n; ++j){
            dist[i][j] = d[i][j] = MOD;
            if(s[i][j] == 'H') q.push({i, j}), dist[i][j] = 0;
            else if(s[i][j] == 'M') q1.push({i, j}), d[i][j] = 0, bx = i, by = j;
            else if(s[i][j] == 'D') ax = i, ay = j;
        }
    } 
    while(!q.empty()){
        int x = q.front()[0], y = q.front()[1];
        q.pop();
        for(int i = 0; i < 4; ++i){
            int a = x + arr[i][0];
            int b = y + arr[i][1];
            if(a>=0&&a<n&&b>=0&&b<n&&s[a][b]=='D'){
                dist[a][b] = min(dist[a][b], dist[x][y] + 1);
            }
            if(a<0||b<0||a==n||b==n||(s[a][b]!='G'&&s[a][b]!='M')) continue;
            if(dist[a][b] > dist[x][y] + 1) {
                dist[a][b] = dist[x][y] + 1;
                q.push({a, b});
            }
        }
    }   
    while(!q1.empty()){
        int x = q1.front()[0], y = q1.front()[1];
        q1.pop();
        for(int i = 0; i < 4; ++i){
            for(int f = 1; f <= S; ++f){
                int a = x + f * arr[i][0];
                int b = y + f * arr[i][1];
                if(a<0||b<0||a>=n||b>=n||(s[a][b]!='G'&&s[a][b]!='M'&&s[a][b]!='D')||d[a][b] < d[x][y] + 1) break;
                d[a][b] = d[x][y] + 1;
                q1.push({a, b});
            }
        }
    }   
   
    int l = 0, r = n*n, ans = -1;
    while(l <= r){
        int m = (l+r)>>1;
        bool ok = 0;
        for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) vis[i][j] = 0;
        q.push({ax, ay});
        vis[ax][ay] = 1;
        while(!q.empty()){  
            int x = q.front()[0], y = q.front()[1];
            q.pop();
            if(dist[x][y] - m <= d[x][y]){
                continue;
            }
            if(x == bx && y == by){
                ok = 1;
                break;
            }
            for(int i = 0; i < 4; ++i){
                for(int f = 1; f <= S; ++f){
                    int a = x + f * arr[i][0];
                    int b = y + f * arr[i][1];
                    if(a<0||b<0||a>=n||b>=n||(s[a][b]!='G'&&s[a][b]!='M')||vis[a][b]) break;
                    vis[a][b] = 1;
                    q.push({a, b});
                }
            }    
        }
        if(ok){
            ans = m;
            l = m + 1;
        }else r = m - 1;
    }
    cout << ans;
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:105:16: warning: unused variable 'aa' [-Wunused-variable]
  105 |     int T = 1, aa;
      |                ^~

Subtask #1
24.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 31580 KB Output is correct
2 Incorrect 15 ms 31640 KB Output isn't correct
3 Correct 16 ms 31636 KB Output is correct
4 Incorrect 16 ms 31700 KB Output isn't correct
5 Incorrect 16 ms 31612 KB Output isn't correct
6 Incorrect 15 ms 31700 KB Output isn't correct
7 Runtime error 171 ms 65536 KB Execution killed with signal 9
8 Runtime error 202 ms 65536 KB Execution killed with signal 9
9 Correct 17 ms 31788 KB Output is correct
10 Incorrect 17 ms 31784 KB Output isn't correct
11 Correct 16 ms 31700 KB Output is correct
12 Incorrect 18 ms 32100 KB Output isn't correct
13 Correct 16 ms 32092 KB Output is correct
14 Correct 26 ms 32508 KB Output is correct
15 Correct 16 ms 31700 KB Output is correct
16 Correct 16 ms 31828 KB Output is correct
17 Correct 15 ms 31828 KB Output is correct
18 Incorrect 16 ms 31764 KB Output isn't correct
19 Correct 16 ms 31828 KB Output is correct
20 Correct 15 ms 31836 KB Output is correct
21 Correct 16 ms 31956 KB Output is correct
22 Incorrect 16 ms 31956 KB Output isn't correct
23 Correct 16 ms 32084 KB Output is correct
24 Incorrect 16 ms 32084 KB Output isn't correct
25 Correct 19 ms 32176 KB Output is correct
26 Incorrect 17 ms 32080 KB Output isn't correct
27 Correct 16 ms 32212 KB Output is correct
28 Incorrect 16 ms 32212 KB Output isn't correct
29 Correct 16 ms 32340 KB Output is correct
30 Incorrect 16 ms 32260 KB Output isn't correct
31 Correct 16 ms 32272 KB Output is correct
32 Incorrect 16 ms 32212 KB Output isn't correct
33 Correct 20 ms 34848 KB Output is correct
34 Correct 21 ms 34768 KB Output is correct
35 Incorrect 30 ms 35520 KB Output isn't correct
36 Correct 23 ms 35316 KB Output is correct
37 Incorrect 29 ms 35288 KB Output isn't correct
38 Incorrect 33 ms 36276 KB Output isn't correct
39 Correct 23 ms 35796 KB Output is correct
40 Incorrect 25 ms 35828 KB Output isn't correct
41 Correct 31 ms 37112 KB Output is correct
42 Correct 24 ms 36308 KB Output is correct
43 Correct 25 ms 36272 KB Output is correct
44 Incorrect 32 ms 37780 KB Output isn't correct
45 Correct 33 ms 36692 KB Output is correct
46 Correct 34 ms 36756 KB Output is correct
47 Incorrect 36 ms 38612 KB Output isn't correct
48 Correct 27 ms 37224 KB Output is correct
49 Incorrect 29 ms 37244 KB Output isn't correct
50 Incorrect 41 ms 39452 KB Output isn't correct
51 Correct 28 ms 37716 KB Output is correct
52 Correct 35 ms 37848 KB Output is correct
53 Correct 48 ms 40416 KB Output is correct
54 Correct 35 ms 38220 KB Output is correct
55 Correct 34 ms 38288 KB Output is correct
56 Incorrect 50 ms 41296 KB Output isn't correct
57 Correct 34 ms 38732 KB Output is correct
58 Incorrect 33 ms 38760 KB Output isn't correct
59 Incorrect 51 ms 41428 KB Output isn't correct
60 Correct 36 ms 39244 KB Output is correct
61 Correct 41 ms 39340 KB Output is correct
62 Incorrect 61 ms 42400 KB Output isn't correct
63 Incorrect 78 ms 39304 KB Output isn't correct
64 Incorrect 145 ms 39348 KB Output isn't correct
65 Incorrect 157 ms 39364 KB Output isn't correct
66 Incorrect 93 ms 39280 KB Output isn't correct
67 Correct 59 ms 39348 KB Output is correct
68 Incorrect 57 ms 39480 KB Output isn't correct
69 Incorrect 60 ms 39492 KB Output isn't correct
70 Incorrect 58 ms 39364 KB Output isn't correct
71 Incorrect 70 ms 39360 KB Output isn't correct
72 Correct 69 ms 39372 KB Output is correct
73 Runtime error 191 ms 65536 KB Execution killed with signal 9
74 Incorrect 99 ms 43288 KB Output isn't correct
75 Runtime error 181 ms 65536 KB Execution killed with signal 9
76 Runtime error 192 ms 65536 KB Execution killed with signal 9
77 Runtime error 228 ms 65536 KB Execution killed with signal 9
78 Runtime error 208 ms 65536 KB Execution killed with signal 9
79 Incorrect 87 ms 43060 KB Output isn't correct
80 Runtime error 239 ms 65536 KB Execution killed with signal 9
81 Runtime error 176 ms 65536 KB Execution killed with signal 9
82 Runtime error 210 ms 65536 KB Execution killed with signal 9
83 Runtime error 216 ms 65536 KB Execution killed with signal 9
84 Incorrect 105 ms 42724 KB Output isn't correct
85 Runtime error 216 ms 65536 KB Execution killed with signal 9
86 Runtime error 204 ms 65536 KB Execution killed with signal 9
87 Runtime error 447 ms 65536 KB Execution killed with signal 9
88 Runtime error 225 ms 65536 KB Execution killed with signal 9
89 Incorrect 125 ms 43612 KB Output isn't correct
90 Runtime error 246 ms 65536 KB Execution killed with signal 9
91 Incorrect 196 ms 43560 KB Output isn't correct
92 Runtime error 238 ms 65536 KB Execution killed with signal 9