제출 #1288919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288919		abhi_atg	Mecho (IOI09_mecho)	C++20	0 / 100	69 ms	131072 KiB

mecho

// Jai Shree Ram
#include<bits/stdc++.h>
using namespace std;
/* Abhi-Atg */
#define array int n;cin >> n;vector<long long> v(n);f(i,0,n)cin >> v[i];
#define out(_) for (auto &it :_){cout << it << " " ;}cout<<endl;
#define f(i,l,r) for(int i=l;i<r;i++)
#define ff(i,r,l) for(int i=r;i>=l;i--)
#define pb push_back
#define mod 1000000007
#define INDIA 998244353
#define ll long long 
#define all(v) v.begin(),v.end()
#define dbg cout << "Bharat\n"
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define minus cout << "-1\n"

void solve(){
    int n,s;cin >> n >> s;
    vector<string> v(n);
    int mx,my;
    int dx,dy;
    vector<pair<int,int>> q;
    vector<vector<int>> dp(n,vector<int>(n, INDIA));
    f(i,0,n){
        cin >> v[i];
        for(int j=0;j<n;j++){
            if(v[i][j]=='M'){
                mx=i;my=j;
            }else if(v[i][j]=='D'){
                dx=i;dy=j;
            }else if(v[i][j]=='H'){
                q.pb({i,j});
                dp[i][j]=0;
            }
        }
    }
    int xx[]={0,0,1,-1};
    int yy[]={1,-1,0,0};
    for(int i=0;i<q.size();i++){
        for(int j=0;j<4;j++){
            int nx=q[i].first+xx[j];
            int ny=q[i].second+yy[j];
            if(nx>=0 && ny>=0 && nx<n && ny<n && v[nx][ny]!='T' && v[nx][ny]!='D' && dp[nx][ny]>dp[q[i].first][q[i].second]+1){
                dp[nx][ny]=dp[q[i].first][q[i].second]+1;
                q.pb({nx,ny});
            }
        }
    }
    int mn=-1;
    int l=0,r=2;
    while(l<=r){
        int mid=(l+r)/2;
        bool flag=false;
        if(dp[mx][my]>=mid){
            vector<pair<int,int>> q;
            q.push_back({mx,my});
            vector<vector<int>> vis(n,vector<int>(n,INDIA));
            vis[mx][my]=0;
            while(q.size()){
                int val=vis[q[0].first][q[0].second]+1;
                for(int st=0;st<s;st++){
                    vector<pair<int,int>> qq;
                    for(int i=0;i<q.size();i++){
                        for(int j=0;j<4;j++){
                            int nx=q[i].first+xx[j];
                            int ny=q[i].second+yy[j];
                            if(nx>=0 && ny>=0 && nx<n && ny<n && v[nx][ny]!='T' && vis[nx][ny]==INDIA && mid<=dp[nx][ny]-val){
                                vis[nx][ny]=val;
                                qq.pb({nx,ny});
                                if(nx==dx && ny==dy){
                                    flag=true;
                                    break;
                                }
                            }
                        }
                        if(flag)break;
                    }
                    q=qq;
                }
            }
        }
        if(flag){
            mn=mid;
            l=mid+1;
        }else r=mid-1;
    }
    cout << mn << "\n";
}


int main(){

    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    // freopen("input.in", "r", stdin);
    // freopen("output.out", "w", stdout);

    int t=1;
    // cin >> t;
    for(int _=1;_<=t;_++){
        // cout<<"Case #"<<_<<": ";
        solve();
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

mecho.cpp: In function 'int main()':
mecho.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100