제출 #1251760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251760		Minbaev	Mecho (IOI09_mecho)	C++20	100 / 100	272 ms	26372 KiB

mecho

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define int     long long
#define ar      array
#define mrand(a, b)   uniform_int_distribution<int>(a, b)(rng)

template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}

template<class T> using ste = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

namespace FAST {
    template<typename T, typename F>
    istream &operator>>(istream &cin, pair<T, F> &p) {
        cin >> p.first >> p.second;
        return cin;
    }

    template<typename T, typename F>
    ostream &operator<<(ostream &cout, pair<T, F> &p) {
        cout << p.first << ' ' << p.second;
        return cout;
    }

    template<typename T>
    istream &operator>>(istream &cin, vector<T> &a) {
    for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, vector<T> &a) {
          for (T i: a) cout << i << ' ';
        return cout;
    }

    template<typename T>
    istream &operator>>(istream &cin, deque<T> &a) {
        for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, deque<T> &a) {
        for (T i: a) cout << i << ' ';
        return cout;
    }
}
using namespace FAST;

const int inf = 1e17 + 7;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
const int md = 998244353;

int binpow(int a, int b, int m){
    if(b == 0)return 1;
    if(b % 2 == 0){
        int c = binpow(a,b/2,m);
        return (c*c)%m;
    }
    return (binpow(a,b-1,m)*a)%m;
}

int divi(int a, int b, int m){
    return (a*(binpow(b,m-2, m)))%m;
}

struct Bit {
    vector<int> b, b2;
    int n;

    Bit(int n) {
        this->n = n + 1;
        b.assign(n + 1, 0);
        b2.assign(n+1, 0);
    }

    void add(vector<int>&b, int idx, int x){
        while(idx <= n){
            b[idx] += x;
            idx += idx & -idx;
        }
    }

    void update(int l, int r, int x){
        add(b, l, x);
        add(b, r+1, -x);
        add(b2, l, x*(l-1));
        add(b2, r+1, -x*r);
    }

    int sum(vector<int>&b, int idx){
        int res = 0;
        while(idx > 0){
            res += b[idx];
            idx -= idx & -idx;
        }
        return res;
    }

    int pref(int idx){
        return sum(b, idx) * idx - sum(b2, idx);
    }

    int get(int l, int r){                  
        return pref(r) - pref(l-1);
    }
};

int n,m,k;

vector<int>dx = {1, -1, 0, 0};
vector<int>dy = {0, 0, 1, -1};

void solve(){

    cin >> n >> k;
    m = n;
    char arr[n][m];
    vector<vector<int>>dist(n+1, vector<int>(m+1, inf));
    vector<vector<ar<int,2>>>dp(n+1, vector<ar<int,2>>(m+1, {inf, -inf}));

    queue<ar<int,2>>q;

    int a1,b1,a2,b2;

    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            cin >> arr[i][j];
            if(arr[i][j] == 'H'){
                q.push({i, j});
                dist[i][j] = 0;
            }
            if(arr[i][j] == 'M'){
                a1 = i;
                b1 = j;
            }
            if(arr[i][j] == 'D'){
                a2 = i;
                b2 = j;
            }
        }
    }

    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop();

        for(int i = 0;i<4;i++){
            int a = x + dx[i];
            int b = y + dy[i];
            if(0 <= a && a < n && 0 <= b && b < m  && (arr[a][b] == 'M' || arr[a][b] == 'G') && umin(dist[a][b], dist[x][y] + 1)){
                q.push({a, b});
            }
        }
    }   

    
    /*for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(dist[i][j] == inf)cout << -1 << " ";
            else
            cout << dist[i][j] << " ";
        }
        cout << "\n";
    }*/

    int l = 0, r = mod, ans = -1;
    while(l <= r){
        int mid = (l + r) / 2;

        vector<vector<ar<int,2>>>dp(n+1, vector<ar<int,2>>(n+1, {inf, inf}));

        queue<ar<int,4>>q;
        dp[a1][b1] = {mid, 0};
        q.push({mid, 0, a1, b1});

        if(mid >= dist[a1][b1])q.pop();

        while(!q.empty()){
            auto [cnt, step, x, y] = q.front();
            q.pop();

            for(int i = 0;i<4;i++){
                int a = x + dx[i];
                int b = y + dy[i];
                if(!(0 <= a && a < n && 0 <= b && b < m)){
                    continue;
                } 
                bool flag = (step == k-1);

                int u = cnt + flag;

                if(arr[a][b] == 'T' || arr[a][b] == 'H')continue;

                if(dist[a][b] <= u)continue;

                if(u == dp[a][b][0] && umin(dp[a][b][1], (step + 1) % k)){
                    q.push({u, dp[a][b][1], a, b});
                }
                else if(umin(dp[a][b][0], u)){
                    dp[a][b][1] = (step + 1) % k;
                    q.push({u, dp[a][b][1], a, b});
                }
            }
        }
        // cout << l << " " << r << "\n";
        // if(mid == 1){
            // for(int i = 0;i<n;i++){
                // for(int j = 0;j<n;j++){
                    // if(dp[i][j][0] == inf)cout << -1 << " ";
                    // else cout << dp[i][j][0] << " ";
                // }
                // cout << "\n";
            // }
        // }

        int cont = dp[a2][b2][0];

        if(dp[a2][b2][0] < inf){
            l = mid + 1;
            ans = mid;
        }
        else r = mid - 1;
        

    }

    cout << ans << "\n";









}
/*

*/
 signed main()
{
//  freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int tt=1; //cin >> tt;
    while(tt--)solve();

}

• Subtask 1: 100 / 100