oj.uz

답안 #1008467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008467 2024-06-26T13:01:30 Z ByeWorld Mecho (IOI09_mecho) C++14
40 / 100
 417 ms 15188 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 1010;
const int MAXA = 2e3+10;
const int INF = 1e18+10;
const int LOG = 63;
const int MOD = 1e9+7;
const int SQRT = 450;
const vector<int> NOL = {};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};

int n, m, k;
char c[MAXN][MAXN];
int dis[MAXN][MAXN], val[MAXN][MAXN];
int sta, en;

bool valid(int x, int y){
    if(x<1 || x>n || y<1 || y>m) return 0;
    if(c[x][y] == 'T') return 0;
    return 1;
}

queue <pii> q;
void bfs(){
    while(!q.empty()){
        int dist = q.front().fi, x = q.front().se/MAXN, y = q.front().se%MAXN;
        q.pop();
        if(dist > dis[x][y]) continue;
        for(int i=0; i<4; i++){
            int nx = x+dx[i], ny = y+dy[i];
            if(!valid(nx, ny)) continue;
            if(c[nx][ny] == 'D') continue;
            if(dis[nx][ny] <= dis[x][y]+k) continue;
            dis[nx][ny] = dis[x][y]+k;
            q.push({dis[nx][ny], nx*MAXN+ny});
        }
    }
}
bool bisa(int num){
    if(dis[sta/MAXN][sta%MAXN] <= num*k) return 0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) val[i][j] = INF;
    q.push({num*k, sta}); val[sta/MAXN][sta%MAXN] = num*k;
    while(!q.empty()){
        int dist = q.front().fi, x = q.front().se/MAXN, y = q.front().se%MAXN;
        q.pop();
        if(dist >= dis[x][y]) continue; // bee ke sini
        if(dist > val[x][y]) continue;
        for(int i=0; i<4; i++){
            int nx = x+dx[i], ny = y+dy[i];
            if(!valid(nx, ny)) continue;
            if(val[nx][ny] <= val[x][y]+1) continue;
            if(dis[nx][ny] <= val[x][y]+1) continue;
            val[nx][ny] = val[x][y]+1;
            q.push({val[nx][ny], nx*MAXN+ny});
        }
    }
    return (val[en/MAXN][en%MAXN] < INF);
}
signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> k; m = n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) dis[i][j] = INF;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> c[i][j];
            if(c[i][j]=='H'){
                q.push({0, i*MAXN+j});
                dis[i][j] = 0;
            } else if(c[i][j]=='D') en = i*MAXN+j;
            else if(c[i][j]=='M') sta = i*MAXN+j;
        }
    }
    bfs();
    // for(int i=1; i<=n; i++){
    //     for(int j=1; j<=m; j++) cout << dis[i][j] << " \n"[j==m];
    // }
    int l=0, r=INF, mid=0, cnt=-1;
    while(l<=r){
        mid = md;
        if(bisa(mid)){ cnt = mid; l = mid+1;}
        else r = mid-1;
    }
    cout << cnt << '\n';
}

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 352 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 342 ms 14896 KB Output isn't correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 960 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 0 ms 604 KB Output is correct
18 Correct 0 ms 856 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 0 ms 600 KB Output is correct
21 Correct 1 ms 704 KB Output is correct
22 Incorrect 1 ms 604 KB Output isn't correct
23 Correct 1 ms 860 KB Output is correct
24 Incorrect 1 ms 860 KB Output isn't correct
25 Correct 1 ms 860 KB Output is correct
26 Incorrect 1 ms 860 KB Output isn't correct
27 Correct 1 ms 860 KB Output is correct
28 Incorrect 1 ms 1116 KB Output isn't correct
29 Correct 1 ms 1116 KB Output is correct
30 Incorrect 2 ms 1116 KB Output isn't correct
31 Correct 1 ms 1116 KB Output is correct
32 Incorrect 1 ms 1116 KB Output isn't correct
33 Correct 9 ms 5468 KB Output is correct
34 Incorrect 34 ms 5600 KB Output isn't correct
35 Incorrect 43 ms 5468 KB Output isn't correct
36 Correct 12 ms 6488 KB Output is correct
37 Incorrect 29 ms 6492 KB Output isn't correct
38 Incorrect 54 ms 6492 KB Output isn't correct
39 Correct 12 ms 7772 KB Output is correct
40 Incorrect 39 ms 7876 KB Output isn't correct
41 Incorrect 98 ms 7772 KB Output isn't correct
42 Correct 19 ms 8908 KB Output is correct
43 Incorrect 40 ms 8932 KB Output isn't correct
44 Incorrect 114 ms 9300 KB Output isn't correct
45 Correct 17 ms 9816 KB Output is correct
46 Incorrect 80 ms 9832 KB Output isn't correct
47 Incorrect 136 ms 9820 KB Output isn't correct
48 Correct 20 ms 10840 KB Output is correct
49 Incorrect 68 ms 10748 KB Output isn't correct
50 Incorrect 141 ms 10848 KB Output isn't correct
51 Correct 30 ms 11780 KB Output is correct
52 Incorrect 76 ms 11612 KB Output isn't correct
53 Incorrect 162 ms 11600 KB Output isn't correct
54 Correct 26 ms 12448 KB Output is correct
55 Incorrect 85 ms 12528 KB Output isn't correct
56 Incorrect 229 ms 12464 KB Output isn't correct
57 Correct 28 ms 13400 KB Output is correct
58 Incorrect 103 ms 13392 KB Output isn't correct
59 Incorrect 258 ms 13400 KB Output isn't correct
60 Correct 32 ms 14364 KB Output is correct
61 Incorrect 123 ms 14420 KB Output isn't correct
62 Incorrect 269 ms 14420 KB Output isn't correct
63 Correct 90 ms 14512 KB Output is correct
64 Incorrect 417 ms 14424 KB Output isn't correct
65 Correct 116 ms 14344 KB Output is correct
66 Correct 107 ms 14508 KB Output is correct
67 Correct 87 ms 14416 KB Output is correct
68 Incorrect 409 ms 14572 KB Output isn't correct
69 Incorrect 301 ms 14448 KB Output isn't correct
70 Incorrect 402 ms 14568 KB Output isn't correct
71 Correct 43 ms 14416 KB Output is correct
72 Incorrect 263 ms 14416 KB Output isn't correct
73 Correct 54 ms 15188 KB Output is correct
74 Incorrect 348 ms 15008 KB Output isn't correct
75 Correct 63 ms 14932 KB Output is correct
76 Correct 57 ms 14932 KB Output is correct
77 Incorrect 346 ms 15016 KB Output isn't correct
78 Correct 67 ms 14932 KB Output is correct
79 Incorrect 310 ms 14932 KB Output isn't correct
80 Correct 65 ms 14932 KB Output is correct
81 Correct 61 ms 14932 KB Output is correct
82 Incorrect 298 ms 14820 KB Output isn't correct
83 Correct 70 ms 14760 KB Output is correct
84 Incorrect 288 ms 14928 KB Output isn't correct
85 Incorrect 290 ms 14928 KB Output isn't correct
86 Correct 63 ms 14928 KB Output is correct
87 Incorrect 274 ms 14932 KB Output isn't correct
88 Incorrect 306 ms 14672 KB Output isn't correct
89 Incorrect 308 ms 14836 KB Output isn't correct
90 Incorrect 310 ms 14592 KB Output isn't correct
91 Incorrect 321 ms 14828 KB Output isn't correct
92 Incorrect 298 ms 14672 KB Output isn't correct