제출 #1257936

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257936		warlock	Mecho (IOI09_mecho)	C++20	61 / 100	212 ms	11280 KiB

mecho

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

using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define int long long int
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define all(x) begin(x),end(x)
#define rev(x) rbegin(x),rend(x)
#define min_priority_queue(x) priority_queue<x, vector<x>,greater<x>>
const int MOD = 1000000007;
const int INF = 1e18;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

void arrin(vi&x,int n){ for(int i=0;i<n;i++){cin >> x[i];}}
void arrout(vi&x){ for(int i=0;i<x.size();i++){cout<< x[i]<<" ";}cout<< endl;}
void pr_bool(bool i){ cout << (i ? "YES" : "NO") << endl;}

int gcd(int a,int b){ if(b==0) return a; return gcd(b, a%b);}
int lcm(int a,int b){ return a/gcd(a,b)*b;}

bool bfs2(int si,int sj,vvi& dist,vector<string>& x,int s,pii des,int m){
    int n = x.size();
    vvi dist2(n,vi(n,-1));
    queue<array<int,4>> q;
    q.push({si,sj,m,0});
    while(!q.empty()){
        int sz=q.size();
        while(sz--){
            auto [i,j,dis,cnt]=q.front();
            q.pop();
            int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
            for(int k=0;k<4;k++){
                int ni=i+dx[k], nj=j+dy[k];
                if(ni<0||nj<0||ni>=n||nj>=n||x[ni][nj]=='T') continue;
                int newDis = dis, newCnt = cnt+1;
                if(newCnt == s){
                    newDis++;
                    newCnt = 0;
                }
                if(dist[ni][nj] - newDis > dist2[ni][nj]){
                    dist2[ni][nj] = dist[ni][nj] - newDis;
                    q.push({ni,nj,newDis,newCnt});
                }
            }
        }
    }
    return dist2[des.first][des.second] != -1;
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,s; cin >> n >> s;
    vector<string> x(n);
    pii st,des,hive;
    for(int i = 0;i < n;i++){
        cin >> x[i];
    }
    queue<pair<pii,int>> hives;
    vvi dist(n,vi(n,-1));
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(x[i][j] == 'H'){
                dist[i][j] = 0;
                hives.push({{i,j},0});
            }
            if(x[i][j] == 'M') st = {i,j};
            if(x[i][j] == 'D') des = {i,j};
        }
    }
    vvi dir = {{-1,0},{1,0},{0,1},{0,-1}};
    while(hives.size()){
        int i = hives.front().first.first,j = hives.front().first.second,dis = hives.front().second;
        hives.pop();
        for(auto&u : dir){
            int nx = i + u[0],ny = j + u[1];
            if(nx < 0 || ny < 0 || nx >= n || ny >= n || x[nx][ny] == 'T' || dist[nx][ny] != -1) continue;
            dist[nx][ny] = dis + 1;
            hives.push({{nx,ny},dis+1});
        }
    }
    // for(int i = 0;i < n;i++){
    //     arrout(dist[i]);
    // }
    int ans = -1;
    int l = 0,r = dist[des.first][des.second];
    while(l <= r){
        int m = (l+r)/2;
        if(bfs2(st.first,st.second,dist,x,s,des,m)){
            ans = m;
            l = m+1;
        }
        else{
            r = m-1;
        }
    }
    cout << ans-1 << endl;
}
// 07:30:10

• Subtask 1: 61 / 100