oj.uz

Submission #953983

# Submission time Handle Problem Language Result Execution time Memory
953983 2024-03-27T03:47:34 Z Github Mecho (IOI09_mecho) C++17
4 / 100
 191 ms 23092 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <climits>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;

#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long

const ll MAXN = 810;
ll bee[MAXN][MAXN];
ll dist[MAXN][MAXN];
pair<ll,ll> parent[MAXN][MAXN];
bool vis[MAXN][MAXN];
ll dX[] = {1, -1, 0, 0};
ll dY[] = {0, 0, 1, -1};
pair<ll, ll> mencho, den;
vector<string> grid;
ll n, s;

bool compute(ll k){
    if (k >= bee[mencho.first][mencho.second]){
        return false;
    }
    for (ll i = 0; i < MAXN; i++){
        for (ll j = 0; j < MAXN; j++){
            dist[i][j] = 1e9;
            parent[i][j] = {-1, -1};
            vis[i][j] = false;
        }
    }
    queue<pair<ll, ll>> q;
    q.push(mencho);
    dist[mencho.first][mencho.second] = 0;
    while (!q.empty()){
        ll x = q.front().first, y = q.front().second; q.pop();
        vis[x][y] = true;
        if (make_pair(x, y) == den){
            break;
        }
        for (ll i = 0; i < 4; i++){
            ll nX = x + dX[i], nY = y+dY[i];
            /*bool b1 = nX < 0 || nX >= n || nY < 0 || nY >= n, b2 = grid[nX][nY] == 'T' || grid[nX][nY] == 'H' || grid[nX][nY] == 'D';
            if (b1 || b2){
                continue;
            }*/
            if (nX < 0 || nX >= n || nY < 0 || nY >= n || grid[nX][nY] == 'T' || grid[nX][nY] == 'H' || grid[nX][nY] == 'D'){
                continue;
            }
            if (dist[nX][nY] > dist[x][y]+1 && !vis[nX][nY] && (bee[nX][nY]-k) > (dist[x][y]+1)/s){
                dist[nX][nY] = dist[x][y]+1;
                parent[nX][nY] = {x, y};
                q.push({nX, nY});
            }
        }
    }
    for (int i = 0; i < 4; i++){
        ll nX = den.first+dX[i], nY = den.second+dY[i];
        /*bool b1 = nX < 0 || nX >= n || nY < 0 || nY >= n, b2 = grid[nX][nY] == 'T' || grid[nX][nY] == 'H';
        if (b1 || b2) {
            continue;
        }
        if ((bee[nX][nY]-k) > (dist[nX][nY])/s){
            return true;
        }*/
        if (nX < 0 || nX >= n || nY < 0 || nY >= n || grid[nX][nY] == 'T' || grid[nX][nY] == 'H') {
            continue;
        }
    }
    return false;
}

int main() {
    speedup
    cin >> n >> s;
    grid.resize(n);
    vector<pair<ll, ll>> start;
    for (ll i = 0; i < n; i++){
        string st; cin >> st;
        grid[i] = st;
        for (ll j = 0; j < n; j++){
            if (st[j] == 'H'){
                start.push_back({i, j});
            }else if (st[j] == 'M'){
                mencho = {i, j};
            }else if (st[j] == 'D'){
                den = {i, j};
            }
        }
    }
    for (ll i = 0; i < MAXN; i++){
        for (ll j = 0; j < MAXN; j++){
            bee[i][j] = 1e9;
            vis[i][j] = false;
        }
    }
    queue<pair<ll, ll>> q;
    for (pair<ll, ll> p: start){
        bee[p.first][p.second] = 0;
        q.push({p.first, p.second});
    }
    while (!q.empty()){
        ll x = q.front().first, y = q.front().second; q.pop();
        vis[x][y] = true;
        for (ll i = 0; i < 4; i++){
            ll nX = x + dX[i], nY = y+dY[i];
            if (nX < 0 || nX >= n || nY < 0 || nY >= n || grid[nX][nY] == 'T' || grid[nX][nY] == 'D'){
                continue;
            }
            if (bee[nX][nY] > bee[x][y]+1 && !vis[nX][nY]){
                bee[nX][nY] = bee[x][y]+1;
                q.push({nX, nY});
            }
        }
    }
    ll l = 0, h = 1e9, mid, ans = -1;
    while (l <= h){
        mid = (l+h)/2;
        if (compute(mid)){
            ans = mid;
            l = mid+1;
        }else{
            h = mid-1;
        }
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
4.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 21592 KB Output isn't correct
2 Incorrect 5 ms 21596 KB Output isn't correct
3 Incorrect 4 ms 21596 KB Output isn't correct
4 Incorrect 5 ms 21592 KB Output isn't correct
5 Incorrect 4 ms 21632 KB Output isn't correct
6 Incorrect 6 ms 21596 KB Output isn't correct
7 Incorrect 114 ms 22536 KB Output isn't correct
8 Correct 7 ms 21596 KB Output is correct
9 Incorrect 6 ms 21596 KB Output isn't correct
10 Incorrect 6 ms 21640 KB Output isn't correct
11 Incorrect 5 ms 21596 KB Output isn't correct
12 Incorrect 9 ms 21596 KB Output isn't correct
13 Incorrect 4 ms 21592 KB Output isn't correct
14 Correct 7 ms 21596 KB Output is correct
15 Incorrect 8 ms 21596 KB Output isn't correct
16 Incorrect 9 ms 21640 KB Output isn't correct
17 Incorrect 10 ms 21636 KB Output isn't correct
18 Incorrect 9 ms 21648 KB Output isn't correct
19 Incorrect 10 ms 21596 KB Output isn't correct
20 Incorrect 9 ms 21596 KB Output isn't correct
21 Incorrect 11 ms 21596 KB Output isn't correct
22 Incorrect 10 ms 21596 KB Output isn't correct
23 Incorrect 12 ms 21596 KB Output isn't correct
24 Incorrect 12 ms 21652 KB Output isn't correct
25 Incorrect 12 ms 21592 KB Output isn't correct
26 Incorrect 11 ms 21596 KB Output isn't correct
27 Incorrect 13 ms 21596 KB Output isn't correct
28 Incorrect 12 ms 21592 KB Output isn't correct
29 Incorrect 13 ms 21596 KB Output isn't correct
30 Incorrect 12 ms 21656 KB Output isn't correct
31 Incorrect 12 ms 21660 KB Output isn't correct
32 Incorrect 12 ms 21596 KB Output isn't correct
33 Incorrect 27 ms 21596 KB Output isn't correct
34 Incorrect 33 ms 21592 KB Output isn't correct
35 Incorrect 27 ms 21596 KB Output isn't correct
36 Incorrect 33 ms 22080 KB Output isn't correct
37 Incorrect 44 ms 21596 KB Output isn't correct
38 Incorrect 32 ms 21596 KB Output isn't correct
39 Incorrect 36 ms 21852 KB Output isn't correct
40 Incorrect 43 ms 21852 KB Output isn't correct
41 Incorrect 38 ms 21852 KB Output isn't correct
42 Incorrect 43 ms 21848 KB Output isn't correct
43 Incorrect 51 ms 21852 KB Output isn't correct
44 Incorrect 71 ms 21912 KB Output isn't correct
45 Incorrect 47 ms 21960 KB Output isn't correct
46 Incorrect 57 ms 21848 KB Output isn't correct
47 Incorrect 68 ms 21848 KB Output isn't correct
48 Incorrect 63 ms 21852 KB Output isn't correct
49 Incorrect 68 ms 22104 KB Output isn't correct
50 Incorrect 73 ms 22040 KB Output isn't correct
51 Incorrect 60 ms 22360 KB Output isn't correct
52 Incorrect 99 ms 22104 KB Output isn't correct
53 Incorrect 88 ms 22104 KB Output isn't correct
54 Incorrect 69 ms 22164 KB Output isn't correct
55 Incorrect 92 ms 22104 KB Output isn't correct
56 Incorrect 102 ms 22172 KB Output isn't correct
57 Incorrect 81 ms 22236 KB Output isn't correct
58 Incorrect 95 ms 22108 KB Output isn't correct
59 Incorrect 175 ms 22104 KB Output isn't correct
60 Incorrect 84 ms 22108 KB Output isn't correct
61 Incorrect 117 ms 22356 KB Output isn't correct
62 Incorrect 147 ms 22328 KB Output isn't correct
63 Incorrect 98 ms 22332 KB Output isn't correct
64 Incorrect 191 ms 22108 KB Output isn't correct
65 Incorrect 185 ms 22356 KB Output isn't correct
66 Incorrect 147 ms 22324 KB Output isn't correct
67 Correct 105 ms 22320 KB Output is correct
68 Incorrect 59 ms 22376 KB Output isn't correct
69 Incorrect 51 ms 22364 KB Output isn't correct
70 Incorrect 42 ms 22360 KB Output isn't correct
71 Incorrect 37 ms 22360 KB Output isn't correct
72 Incorrect 61 ms 22372 KB Output isn't correct
73 Incorrect 25 ms 22876 KB Output isn't correct
74 Incorrect 120 ms 22904 KB Output isn't correct
75 Incorrect 87 ms 22912 KB Output isn't correct
76 Incorrect 67 ms 22876 KB Output isn't correct
77 Incorrect 77 ms 22872 KB Output isn't correct
78 Correct 80 ms 23092 KB Output is correct
79 Incorrect 113 ms 22620 KB Output isn't correct
80 Incorrect 82 ms 22844 KB Output isn't correct
81 Incorrect 73 ms 22616 KB Output isn't correct
82 Incorrect 99 ms 22608 KB Output isn't correct
83 Incorrect 121 ms 22620 KB Output isn't correct
84 Incorrect 166 ms 22620 KB Output isn't correct
85 Incorrect 96 ms 22756 KB Output isn't correct
86 Incorrect 98 ms 22768 KB Output isn't correct
87 Incorrect 112 ms 22620 KB Output isn't correct
88 Incorrect 117 ms 22620 KB Output isn't correct
89 Incorrect 174 ms 22652 KB Output isn't correct
90 Incorrect 118 ms 22620 KB Output isn't correct
91 Incorrect 112 ms 22648 KB Output isn't correct
92 Incorrect 92 ms 22644 KB Output isn't correct