Submission #1268221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268221		Bui_Quoc_Cuong	Mecho (IOI09_mecho)	C++20	84 / 100	186 ms	12068 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define sz(v) (int)v.size()
#define fi first
#define se second
#define ALL(A) A.begin(), A.end()
#define compact(v) v.erase(unique(ALL(v)), end(v))

#define FOR(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FORD(i, a, b) for(int i = (a); i >= (int)(b); i--)
#define BIT(mask,i) ((mask>>(i))&1)
#define MASK(a) (1LL << (a))

#define lwb lower_bound
#define upb upper_bound

#define dbg(x) "[" #x " = " << (x) << "]"
#define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true;
    return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true;
    return false;
}

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using vpi = vector<pii>;
using vpl = vector<pll>;

const int dx[] = {0, 0, 1, - 1};
const int dy[] = {- 1, 1, 0, 0};

int n, S;
char a[805][805];
ll dist[805][805];
ll f[805][805];

int sx, sy, fx, fy;

bool check(int T){
    FOR(i, 1, n) FOR(j, 1, n){
        f[i][j] = 1e18;
    }
    if(dist[sx][sy] <= T * S) return 0;
    queue <pair <int, int>> que;
    f[sx][sy] = 1LL * T * S;    
    que.push({sx, sy});
    while(!que.empty()){
        int u = que.front().fi, v = que.front().se;
        que.pop();
        FOR(s, 0, 3){
            int x = u + dx[s], y = v + dy[s];
            if(x < 1 || x > n || y < 1 || y > n || a[x][y] == 'T') continue;    
            ll t = (f[u][v] + 1) / S;   
            if(t >= dist[x][y] / S) continue;
            if (x == fx && y == fy) return 1;
            if(minimize(f[x][y], f[u][v] + 1)){
                que.push({x, y});
            }
        }
    }
    return (f[fx][fy] < 1e18);
}

void solve(){   
    cin >> n >> S;
    FOR(i, 1, n) FOR(j, 1, n){
        cin >> a[i][j];
        if(a[i][j] == 'D'){
            fx = i;
            fy = j;
        }
        if(a[i][j] == 'M'){
            sx = i;
            sy = j;
        }   
    }
    if(fx == 0 && fy == 0){
        cout << - 1;
        return;
    }
    #define bg array <ll, 3>
    priority_queue <bg, vector <bg>, greater <bg>> pq;
    FOR(i, 1, n) FOR(j, 1, n){
        dist[i][j] = 1e18;
        if(a[i][j] == 'H'){
            dist[i][j] = 0;
            pq.push({0, i, j});
        }
    }
    while(!pq.empty()){
        ll cost = pq.top()[0];
        int u = pq.top()[1], v = pq.top()[2];
        pq.pop();
        if(cost > dist[u][v]) continue;
        FOR(s, 0, 3){
            int x = u + dx[s], y = v + dy[s];
            if(x < 1 || x > n || y < 1 || y > n || a[x][y] == 'T') continue;
            if(minimize(dist[x][y], dist[u][v] + S)){
                pq.push({dist[x][y], x, y});
            }
        }
    }
    int l = 0, r = n * n, ans = - 1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }   
    cout << ans;
}

int main(void){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    file("chugautimduong");
            
    int tc = 1; // cin >> tc;
    while (tc--) solve();

    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:22:55: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
      |                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:134:5: note: in expansion of macro 'file'
  134 |     file("chugautimduong");
      |     ^~~~
mecho.cpp:22:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
      |                                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:134:5: note: in expansion of macro 'file'
  134 |     file("chugautimduong");
      |     ^~~~

• Subtask 1: 84 / 100