Submission #1201014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201014		ppppp	Mecho (IOI09_mecho)	C++20	5 / 100	92 ms	12104 KiB

mecho

#include<bits/stdc++.h>
#define int long long int
#define f first 
// #define s second 
using namespace std;
int di[4] = {0, 0, 1, -1};
int dj[4] = {-1, 1, 0, 0};

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n, s;
    cin >> n >> s;
    vector<string> mat(n, "");
    vector<vector<int>> time(n, vector<int>(n, 0));
    int si, sj, ei, ej;
    queue<pair<int,pair<int,int>>> bag;
    vector<vector<bool>> v(n, vector<bool>(n, 0));
    for (int i = 0 ; i < n ; i++) cin >> mat[i];
    // cout << -1;
    for (int i = 0 ; i < n ; i++) { 
        for (int j = 0 ; j < n ; j++) {
            if (mat[i][j] == 'M') {
                si = i;
                sj = j;
            } else if (mat[i][j] == 'D') {
                ei = i;
                ej = j;
            } else if (mat[i][j] == 'H') {
                bag.push({0, {i, j}});
                v[i][j] = 1;
            }
        }
    }
    while(!bag.empty()) {
        int cnt = bag.front().first;
        int i = bag.front().second.first;
        int j = bag.front().second.second;
        bag.pop();
        for (int d = 0 ; d < 4 ; d++) {
            int nxi = i + di[d];
            int nxj = j + dj[d];
            if (nxi >= 0 && nxi < n && nxj >= 0 && nxj < n && mat[nxi][nxj] != 'T') {
                if (v[nxi][nxj]) continue;
                bag.push({cnt+1, {nxi, nxj}});
                v[nxi][nxj] = 1;
                time[nxi][nxj] = cnt+1;
            }   
        }
    }
    // for (int i = 0 ; i < n ; i++) {
    //     for (int j = 0 ; j < n ; j++) cout << time[i][j] << ' ';
    //     cout << endl;
    // }
    int l = 0;
    int r = 1e9;
    // bool valid = 0;
    vector<int> valid(n*n, 0);
    int ans = 1e9;
    while(l < r) {
        int mid = (l+r+1)/2;
        // cout << mid << endl;
        if (mid >= time[si][sj]) r = mid-1;
        else {
            bag.push({mid*s, {si, sj}});
            v.resize(0);
            v.resize(n, vector<bool>(n, 0));
            v[si][sj] = 1;
            // cout << bag.size() << endl;
            while(!bag.empty()) {
                int cnt = bag.front().first;
                int i = bag.front().second.first;
                int j = bag.front().second.second;
                // cout << i << ' ' << j << ' ' << cnt << endl;
                bag.pop();
                if (i == ei && j == ej) {
                    l = mid;
                    ans = min(ans, l);
                    break;
                }
                for (int d = 0 ; d < 4 ; d++) {
                    int nxi = i + di[d];
                    int nxj = j + dj[d];
                    if (nxi >= 0 && nxi < n && nxj >= 0 && nxj < n && mat[nxi][nxj] != 'T') {
                        if (!v[nxi][nxj] && (cnt) < time[nxi][nxj]*s) {
                            bag.push({cnt+1, {nxi, nxj}});
                            v[nxi][nxj] = 1;
                        }
                    }
                }
            }
            if (bag.empty()) r = mid-1;
            else {
                while(!bag.empty()) {
                    bag.pop();
                }
            }
        }
    }
    if (ans == 1e9) cout << -1;
    else cout << ans;
    // if (valid[l]) cout << l;
    // else cout << -1;
}

• Subtask 1: 5 / 100