Submission #1117292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117292		DON_F	Mecho (IOI09_mecho)	C++14	4 / 100	140 ms	6648 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define all(x) x.begin(), x.end()
#define L(i, b, e) for (int i = b; i < e; ++i)
#define R(i, b, e) for (int i = b; i >= e; --i)
#define pb emplace_back
#define vi vector<int>
#define sz(x) ((int) x.size())
const int N = 8e2 + 7, Mx = 1e9 + 9;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int n, s;
string a[N];
int dis1[N][N], dis2[N][N];
pair<int, int> st, d;
bool in(int x, int y){
    return (x >= 0 && y >= 0 && x < n && y < n && a[x][y] != 'T');
}
int work(int m){
    L(i, 0, n)L(j, 0, n)dis2[i][j] = Mx;
    queue<tuple<int, int, int>> q;
    q.push({st.first, st.second, s});
    dis2[st.first][st.second] = m;
    while (!q.empty()){
        auto [x, y, p] = q.front();
        q.pop();
        if (p == 0 && dis2[x][y] >= dis1[x][y])continue;
        if (p == 0)p = s;
        L(i, 0, 4){
            int nx = x + dx[i], ny = y + dy[i];
            if (in(nx, ny) && dis2[x][y] + (p == s) <= dis1[nx][ny] && dis2[nx][ny] == Mx && a[nx][ny] != 'H'){
                q.push({nx, ny, p - 1});
                dis2[nx][ny] = dis2[x][y] + (p == s);
            }
        }
    }
    return (dis2[d.first][d.second] != Mx);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> s;
    L(i, 0, n){
        cin >> a[i];
    }
    L(i, 0, n)L(j, 0, n)dis1[i][j] = dis2[i][j] = Mx;
    queue<pair<int, int>> q;
    L(i, 0, n){
        L(j, 0, n){
            if (a[i][j] == 'H'){
                q.push({i, j});
                dis1[i][j] = 0;
            }else if (a[i][j] == 'M'){
                st = {i, j};
            }else if (a[i][j] == 'D'){
                d = {i, j};
            }
        }
    }
    while (!q.empty()){
        auto [x, y] = q.front();
        q.pop();
        L(i, 0, 4){
            int nx = x + dx[i], ny = y + dy[i];
            if (in(nx, ny) && a[nx][ny] != 'D' && dis1[nx][ny] == Mx){
                q.push({nx, ny});
                dis1[nx][ny] = dis1[x][y] + 1;
            }
        }
    }
    int lo = 0, hi = n * n, ans = -1;
    while (lo <= hi){
        int mid = lo + (hi - lo) / 2;
        if (work(mid)){
            ans = mid;
            lo = mid + 1;
        }else{
            hi = mid - 1;
        }
    }
    cout << -1;
}

Compilation message (stderr)

mecho.cpp: In function 'int work(int)':
mecho.cpp:25:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |         auto [x, y, p] = q.front();
      |              ^
mecho.cpp: In function 'int main()':
mecho.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |         auto [x, y] = q.front();
      |              ^
mecho.cpp:72:29: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   72 |     int lo = 0, hi = n * n, ans = -1;
      |                             ^~~

• Subtask 1: 4 / 100