Submission #535828

#	Time	Username	Problem	Language	Result	Execution time	Memory
535828		SlavicG	Mecho (IOI09_mecho)	C++17	100 / 100	186 ms	11360 KiB

mecho

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

#define int long long

const int N = 805;
char c[N][N];
int n, s;
bool ok(int i, int j) {
    return (i >= 0 && j >= 0 && i < n && j < n && c[i][j] != 'T' && c[i][j] != 'H');
}

vector<vector<int>> bfs(vector<pair<int,int>> nodes, char forbidden) {
    vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
    queue<pair<int,int>> q;
    for(auto f: nodes) {
        dist[f.first][f.second] = 0;
        q.push({f.first, f.second});
    }

    while(!q.empty()) {
        int i = q.front().first, j = q.front().second;
        q.pop();
        if(ok(i + 1, j) && c[i + 1][j] != forbidden && dist[i + 1][j] == INT_MAX) {
            dist[i + 1][j] = dist[i][j] + 1;
            q.push({i + 1, j});
        }   
        if(ok(i - 1, j) && c[i - 1][j] != forbidden && dist[i - 1][j] == INT_MAX) {
            dist[i - 1][j] = dist[i][j] + 1;
            q.push({i - 1, j});
        }  

        if(ok(i, j + 1) && c[i][j + 1] != forbidden && dist[i][j + 1] == INT_MAX) {
            dist[i][j + 1] = dist[i][j] + 1;
            q.push({i, j + 1});
        }  

        if(ok(i, j - 1) && c[i][j - 1] != forbidden && dist[i][j - 1] == INT_MAX) {
            dist[i][j - 1] = dist[i][j] + 1;
            q.push({i, j - 1});
        }  
    }
    return dist;
}
vector<vector<int>> bees;
bool dfs(int startx, int starty, int val) {
    queue<pair<pair<int, int>, int>> q;
    q.push({{startx, starty}, 0});
    if(val >= bees[startx][starty]) return false;
    vector<vector<int>> dist(n, vector<int>(n, -1));
    dist[startx][starty] = val;

    while(!q.empty()) {
        int i = q.front().first.first, j = q.front().first.second, moves = q.front().second;
        q.pop();
        if(c[i][j] == 'D') return true;

        if(ok(i + 1, j) && dist[i + 1][j] == -1 && (dist[i][j] + ((moves + 1) % s == 0)) < bees[i + 1][j]) {
            dist[i + 1][j] = dist[i][j] + ((moves + 1) % s == 0);
            q.push({{i + 1, j}, moves + 1});
        }
        if(ok(i - 1, j) && dist[i - 1][j] == -1 && (dist[i][j] + ((moves + 1) % s == 0)) < bees[i - 1][j]) {
            dist[i - 1][j] = dist[i][j] + ((moves + 1) % s == 0);
            q.push({{i - 1, j}, moves + 1});
        }
        if(ok(i, j + 1) && dist[i][j + 1] == -1 && (dist[i][j] + ((moves + 1) % s == 0)) < bees[i][j + 1]) {
            dist[i][j + 1] = dist[i][j] + ((moves + 1) % s == 0);
            q.push({{i, j + 1}, moves + 1});
        }
        if(ok(i, j - 1) && dist[i][j - 1] == -1 && (dist[i][j] + ((moves + 1) % s == 0)) < bees[i][j - 1]) {
            dist[i][j - 1] = dist[i][j] + ((moves + 1) % s == 0);
            q.push({{i, j - 1}, moves + 1});
        }
    }
    return false;

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

    int startx, starty;
    vector<pair<int,int>> f;
    for(int i = 0;i < n; ++i) {
        for(int j = 0;j < n; ++j) {
            cin >> c[i][j];
            if(c[i][j] == 'M') {
                startx = i, starty = j;
            }
            if(c[i][j] == 'H') {
                f.pb({i, j});
            }
        }
    }

    bees = bfs(f, 'D');
    
    int l = 0, r = 1e9;
    int ans = -1;
    while(l <= r) {
        int mid = l + r >> 1;

        if(dfs(startx, starty, mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << "\n";
}
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}

Compilation message (stderr)

mecho.cpp: In function 'void solve()':
mecho.cpp:109:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |         int mid = l + r >> 1;
      |                   ~~^~~
mecho.cpp:111:15: warning: 'starty' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |         if(dfs(startx, starty, mid)) {
      |            ~~~^~~~~~~~~~~~~~~~~~~~~
mecho.cpp:111:15: warning: 'startx' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 100 / 100