oj.uz

답안 #1008431

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008431 2024-06-26T12:24:44 Z ByeWorld Mecho (IOI09_mecho) C++14
28 / 100
 406 ms 15176 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(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
28.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 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 Incorrect 0 ms 348 KB Output isn't correct
7 Incorrect 301 ms 14564 KB Output isn't correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 452 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 1 ms 964 KB Output isn't correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 1 ms 444 KB Output is correct
17 Correct 0 ms 604 KB Output is correct
18 Correct 0 ms 604 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 0 ms 604 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 856 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 1112 KB Output isn't correct
29 Correct 1 ms 1116 KB Output is correct
30 Incorrect 1 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 7 ms 5412 KB Output is correct
34 Incorrect 29 ms 5464 KB Output isn't correct
35 Incorrect 42 ms 5468 KB Output isn't correct
36 Correct 9 ms 6488 KB Output is correct
37 Incorrect 28 ms 6472 KB Output isn't correct
38 Incorrect 51 ms 6492 KB Output isn't correct
39 Correct 11 ms 7772 KB Output is correct
40 Incorrect 36 ms 7804 KB Output isn't correct
41 Incorrect 85 ms 7772 KB Output isn't correct
42 Correct 14 ms 9048 KB Output is correct
43 Incorrect 40 ms 9052 KB Output isn't correct
44 Incorrect 112 ms 9088 KB Output isn't correct
45 Correct 15 ms 9828 KB Output is correct
46 Incorrect 62 ms 9868 KB Output isn't correct
47 Incorrect 134 ms 9808 KB Output isn't correct
48 Correct 19 ms 10840 KB Output is correct
49 Incorrect 64 ms 10712 KB Output isn't correct
50 Incorrect 136 ms 10844 KB Output isn't correct
51 Correct 22 ms 11600 KB Output is correct
52 Incorrect 78 ms 11612 KB Output isn't correct
53 Incorrect 172 ms 11792 KB Output isn't correct
54 Correct 30 ms 12636 KB Output is correct
55 Incorrect 84 ms 12524 KB Output isn't correct
56 Incorrect 211 ms 12656 KB Output isn't correct
57 Correct 26 ms 13396 KB Output is correct
58 Incorrect 107 ms 13404 KB Output isn't correct
59 Incorrect 232 ms 13396 KB Output isn't correct
60 Correct 32 ms 14420 KB Output is correct
61 Incorrect 124 ms 14348 KB Output isn't correct
62 Incorrect 249 ms 14424 KB Output isn't correct
63 Correct 87 ms 14416 KB Output is correct
64 Incorrect 406 ms 14424 KB Output isn't correct
65 Correct 111 ms 14416 KB Output is correct
66 Correct 96 ms 14508 KB Output is correct
67 Correct 89 ms 14484 KB Output is correct
68 Incorrect 370 ms 14564 KB Output isn't correct
69 Incorrect 290 ms 14428 KB Output isn't correct
70 Incorrect 381 ms 14572 KB Output isn't correct
71 Correct 45 ms 14416 KB Output is correct
72 Incorrect 255 ms 14416 KB Output isn't correct
73 Correct 37 ms 14936 KB Output is correct
74 Incorrect 290 ms 15016 KB Output isn't correct
75 Correct 60 ms 15060 KB Output is correct
76 Correct 56 ms 14948 KB Output is correct
77 Incorrect 319 ms 14928 KB Output isn't correct
78 Correct 62 ms 14832 KB Output is correct
79 Incorrect 302 ms 14996 KB Output isn't correct
80 Correct 57 ms 14936 KB Output is correct
81 Correct 66 ms 15008 KB Output is correct
82 Incorrect 295 ms 15176 KB Output isn't correct
83 Correct 90 ms 14724 KB Output is correct
84 Incorrect 301 ms 14744 KB Output isn't correct
85 Incorrect 277 ms 14676 KB Output isn't correct
86 Correct 66 ms 14680 KB Output is correct
87 Incorrect 299 ms 14928 KB Output isn't correct
88 Incorrect 315 ms 14672 KB Output isn't correct
89 Incorrect 334 ms 14964 KB Output isn't correct
90 Incorrect 289 ms 14680 KB Output isn't correct
91 Incorrect 305 ms 14676 KB Output isn't correct
92 Incorrect 288 ms 14672 KB Output isn't correct