Submission #1201080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201080		apelpisia	Mecho (IOI09_mecho)	C++20	8 / 100	1097 ms	131072 KiB

mecho

#include<bits/stdc++.h>

using namespace std;
 
#define ll long long
#define pi pair<int, int>
#define ti tuple<ll, int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

vector<vector<char>> grid;
vector<vector<ll>> t;

vector<pi> direction={{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int n;
ll s;
int si=-1, sj=-1, ei=-1, ej=-1;

bool bfs(ll mid) {
    vector<vector<bool>> visited(n, vector<bool>(n));
    queue<ti> nq;
    
    nq.push({s*mid, si, sj});
    visited[si][sj]=true;
    
    while(nq.size()) {
        auto [cnt, i, j]=nq.front(); nq.pop();

        if(grid[i][j]=='D') return true;
        
        for(auto &[di, dj]: direction) {
            int ni=i+di;
            int nj=j+dj;
            
            if(ni>=0 && nj>=0 && ni<n && nj<n && (cnt+1)<s*t[ni][nj] && grid[ni][nj]!='T' && !visited[ni][nj]) {
                visited[ni][nj]=true;
                nq.push({cnt+1, ni, nj});
            }
        }
    }
    
    return false;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> s;
    
    grid.resize(n, vector<char>(n));
    t.resize(n, vector<ll>(n, LLONG_MAX));
    
    queue<ti> q;
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> grid[i][j];
            
            if(grid[i][j]=='H') {
                q.push({0, i, j});
            } else if(grid[i][j]=='M') {
                si=i;
                sj=j;
            } else if(grid[i][j]=='D') {
                ei=i;
                ej=j;
            }
        }
    }

    
    while(q.size()) {
        auto [cnt, i, j]=q.front(); q.pop();
        
        t[i][j]=cnt;
        
        for(auto &[di, dj]: direction) {
            int ni=i+di;
            int nj=j+dj;
            
            
            if(ni>=0 && nj>=0 && ni<n && nj<n && t[ni][nj]==LLONG_MAX && (grid[ni][nj]!='T' && grid[ni][nj]!='D')) {
                q.push({cnt+1, ni, nj});
            }
        }
    }
    
    ll l=-1, r=INT_MAX;
    
    while(l<r) {
        ll mid=(l+r)/2;
        
        if(bfs(mid)) {
            l=mid;
        } else {
            r=mid-1;
        }
    }
    
    cout << l;
    
    return 0;
}

• Subtask 1: 8 / 100