Submission #657869

#	Time	Username	Problem	Language	Result	Execution time	Memory
657869		burak_ozzkan	Mecho (IOI09_mecho)	C++14	68 / 100	276 ms	10064 KiB

mecho

#include <bits/stdc++.h>
#define nl '\n'
#define int long long
using namespace std;

int n, s;
array<int, 2> starting, ending;

bool bfs(int t, vector< vector<bool> >& vis, vector< vector<char> >& v, vector< vector<int> >& obstacle){
    bool ans = 0;
    queue< array<int, 3> > q;
    q.push({starting[0], starting[1], t*s});
    while(!q.empty()){
        auto top = q.front(); q.pop();
        int i = top[0];
        int j = top[1];
        int currTime = top[2];
        if(i <= -1 || i >= n || j <= -1 || j >= n) continue;
        if(v[i][j] == 'D') ans = 1;
        if(vis[i][j] || v[i][j] == 'T' || obstacle[i][j] <= currTime) continue;
        vis[i][j] = 1;

        q.push({i-1, j, currTime+1});
        q.push({i, j-1, currTime+1});
        q.push({i+1, j, currTime+1});
        q.push({i, j+1, currTime+1});
    }

    return ans;
}

void solve(){
    cin >> n >> s;

    vector< vector<char> > v(n, vector<char>(n));
    queue< array<int, 3> > q; // [0] = i, [1] = j, [2] = time

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> v[i][j];
            if(v[i][j] == 'H') q.push({i, j, 0});
            if(v[i][j] == 'M') starting = {i, j};
            if(v[i][j] == 'D') ending = {i, j};
        }
    }

    vector< vector<int> > obstacle(n, vector<int>(n, 1e9));
    vector< vector<bool> > visB(n, vector<bool>(n, 0));
    while(!q.empty()){
        auto top = q.front(); q.pop();
        int i = top[0];
        int j = top[1];
        int t = top[2];
        if(i <= -1 || i >= n || j <= -1 || j >= n) continue;
        if(visB[i][j] || v[i][j] == 'T' || v[i][j] == 'M' || v[i][j] == 'D') continue;
        visB[i][j] = 1;

        obstacle[i][j] = t*s;
        q.push({i-1, j, t+1});
        q.push({i, j-1, t+1});
        q.push({i+1, j, t+1});
        q.push({i, j+1, t+1});
    }


    int lo = 0;
    int hi = 1e9;
    int ans = INT_MAX;
    while(lo <= hi){
        int mid = lo+(hi-lo)/2;

        vector< vector<bool> > vis(n, vector<bool>(n, 0));
        if(bfs(mid, vis, v, obstacle)){
            ans = mid;
            lo = mid+1;
        } else {
            hi = mid-1;
        }
    }

    cout << ans << nl;
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1; /*cin >> t;*/ while(t--) solve();
}

• Subtask 1: 68 / 100