Submission #395548

#	Time	Username	Problem	Language	Result	Execution time	Memory
395548		AugustinasJucas	Mecho (IOI09_mecho)	C++14	84 / 100	240 ms	8520 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
const int dydis = 1e3 + 10;
const int inf = 1e9;
int n, S;
char mas[dydis][dydis];
int dist[dydis][dydis];
vector<pair<int, int> > dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
void bfs(){
    for(int i = 0; i < dydis; i++) for(int j = 0; j < dydis; j++) dist[i][j] = inf;
    queue<pair<int, int> > q;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(mas[i][j] != 'H') continue;
            dist[i][j] = 0;
            q.push({i, j});
        }
    }
    while(!q.empty()){
        int e = q.front().first;
        int s = q.front().second;
        int pe, ps;
        q.pop();
        for(auto x : dir){
            pe = x.first + e;
            ps = x.second + s;
            if(pe < 0 || ps < 0 || pe >= n || ps >= n) continue;
            if(mas[pe][ps] == 'D' || mas[pe][ps] == 'T') continue;
            if(dist[pe][ps] > dist[e][s] + 1){
                dist[pe][ps] = dist[e][s] + 1;
                q.push({pe, ps});
            }
        }
    }
}
int d[dydis][dydis];
int sE, sS, eE, eS;
bool f(int X){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            d[i][j] = inf;
        }
    }
    queue<pair<int, int> > q;
    d[sE][sS] = 0;
    q.push({sE, sS});
    while(!q.empty()){
        int e = q.front().first;
        int s = q.front().second;
        int pe, ps;
        q.pop();
        for(auto x : dir){
            pe = e + x.first;
            ps = s + x.second;
            if(pe < 0 || ps < 0 || pe >= n || ps >= n) continue;
            if(mas[pe][ps] == 'H' || mas[pe][ps] == 'T') continue;
            int bus = d[e][s] + 1;
            int b1 = bus / S;
            if(b1 >= dist[pe][ps] - X) continue;
            if(d[pe][ps] > bus){
                d[pe][ps] = bus;
                q.push({pe, ps});
            }
        }
    }
    return d[eE][eS] < inf;
}
int main(){
    cin >> n >> S;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> mas[i][j];
            if(mas[i][j] == 'M') sE = i, sS = j;
            if(mas[i][j] == 'D') eE = i, eS = j;

        }
    }
    bfs();
    int l = 0, r = 1e9, mid, ans = -1; 
    while(l <= r){
        mid = (l + r) / 2;
        if(f(mid)){
            ans = max(ans, mid);
            l = mid+1;
        }else{
            r = mid-1;
        }
    }
    cout << ans;
    return 0;
}

• Subtask 1: 84 / 100