제출 #1260793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260793		_unknown_2010	Mecho (IOI09_mecho)	C++20	14 / 100	1097 ms	131072 KiB

mecho

// #ifndef khos
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef khos
    #include "t_debug.cpp"
#else
    #define debug(...) 42
#endif
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using indexed_multiset = tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>;

#define int int64_t
#define vi vector
#define ss second
#define ff first
#define TESTCASES
#define all(x) (x).begin(), (x).end()
const int mod = 1e9+7;
const int MAXN=4e6;
const int inf=1e18;
vi<int> dx={1, -1, 0, 0};
vi<int> dy={0, 0, 1, -1};
void solution() {
    int n,s;
    cin >> n >> s;
    vi<vi<char>> a(n, vi<char> (n));
    vi<vi<int>> dist(n, vi<int> (n, inf));
    queue<pair<int,int>> q;
    int sx, sy, ex, ey;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> a[i][j];
            if(a[i][j]=='H'){
                dist[i][j]=0;
                q.push({i, j});
            }
            if(a[i][j]=='M'){
                sx=i,sy=j;
            }
            if(a[i][j]=='D'){
                ex=i,ey=j;
            }
        }
    }
    auto isvalid = [&](int nx, int ny) -> bool {
        if(nx<0 || ny<0)return 0;
        if(nx>=n || ny>=n)return 0;
        if(a[nx][ny]!='G')return false;
        return true;
    };
    while(!q.empty()){
        int x=q.front().ff;
        int y=q.front().ss;
        q.pop();
        for(int i=0; i<4; i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(isvalid(nx, ny) && dist[x][y]<dist[nx][ny]){
                dist[nx][ny]=dist[x][y]+1;
                q.push({nx, ny});
            }
        }
    }
    int l=-1,r=2*n;
    while(l<r){
        int mid=(l+r+1)/2;
        queue<array<int,4>> q;
        q.push({0, mid, sx, sy});
        map<pair<int,int>, int> mp;
        bool ok=0;
        while(!q.empty()){
            auto [sp, tm, x, y] = q.front();
            q.pop();
            // if(mid==3)debug(sp, tm, x, y);
            for(int i=0; i<4; i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                if(mp[{nx, ny}]>0)continue;
                if(ex==nx && ey==ny){
                    ok=1;
                    break;
                }
                if(isvalid(nx, ny) && dist[nx][ny]>=tm){
                    mp[{nx, ny}]=1;
                    sp=(sp+1)%s;
                    if(sp==0)tm++;
                    if(sp!=0){
                        q.push({sp, tm, nx, ny});
                    }
                    else if(dist[nx][ny]>=tm){
                        q.push({sp, tm, nx, ny});
                    }
                }
            }
            if(ok)break;
        }
        if(ok)l=mid;
        else r=mid-1;
    }
    cout << l;
}
int32_t main(){
    clock_t tStart = clock();
    // freopen("atlarge.in", "r", stdin);
    // freopen("atlarge.out", "w", stdout);
    #ifdef khos
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q = 1;
    #ifdef TESTCASES
        // cin >> q;
    #endif
    while(q--) {
        solution();
        cout << '\n';
    }
    cerr<<fixed<<setprecision(3)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
}

• Subtask 1: 14 / 100