Submission #1284352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284352		quan606303	Mecho (IOI09_mecho)	C++20	100 / 100	176 ms	17376 KiB

mecho

/*
 * @Author: RMQuan 
 * @Date: 2025-10-28 10:51:11 
 * @Last Modified by: RMQuan
 * @Last Modified time: 2025-10-28 10:56:14
 */
/*idea : 



*/
#include <bits/stdc++.h>
bool M1;
#define int long long
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define TASK "TEST"
#define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
using namespace std;
const int MOD=1e9+7;
const int maxn=805;
const int inf=1e18;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
int mn_tm[maxn][maxn];
int a[maxn][maxn],n,s;
bool vst_h[maxn][maxn];
bool vst[maxn][maxn];
int dist[maxn][maxn];
vector<pair<int,int> > S,T,h;
bool check(int x,int y)
{
    return (x>=1&&y>=1&&x<=n&&y<=n);
}
bool check(int mid)
{
    if (mid>=mn_tm[S[0].fi][S[0].se])return false;
    queue<pair<int,int> > q;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            vst[i][j]=0;
            dist[i][j]=inf;
        }
    }
    for (auto i:S)
    {
        q.push(i);
        vst[i.fi][i.se]=true;
        dist[i.fi][i.se]=mid*s;
    }
    while (q.size())
    {
        int x,y;
        tie(x,y)=q.front();
        q.pop();
        for (int i=0;i<4;i++)
        {
            int u=x+dx[i];
            int v=y+dy[i];
            if (check(u,v)&&!vst[u][v]&&a[u][v]&&((dist[x][y]+1)/s<mn_tm[u][v]))
            {
                vst[u][v]=true;
                dist[u][v]=dist[x][y]+1;
                q.push({u,v});
            }
        }
    }
    return vst[T[0].fi][T[0].se];
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    file();
    cin>>n>>s;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            char x;
            cin>>x;
            mn_tm[i][j]=inf;
            if (x=='T')a[i][j]=0;
            else if (x=='G')a[i][j]=1;
            else if (x=='M')
            {
                a[i][j]=1;
                S.push_back({i,j});
            }
            else if (x=='D')
            {
                a[i][j]=2;
                T.push_back({i,j});
            }
            else if (x=='H')
            {
                a[i][j]=1;
                h.push_back({i,j});
            }
        }
    }
    queue<pair<int,int> > q;
    for (auto i:h)
    {
        q.push(i);
        vst_h[i.fi][i.se]=true;
        mn_tm[i.fi][i.se]=0;
    }
    while (q.size())
    {
        int x,y;
        tie(x,y)=q.front();
        q.pop();
        for (int i=0;i<4;i++)
        {
            int u=x+dx[i];
            int v=y+dy[i];
            if (check(u,v)&&a[u][v]==1&&vst_h[u][v]==false)
            {
                vst_h[u][v]=true;
                mn_tm[u][v]=mn_tm[x][y]+1;
                q.push({u,v});
            }
        }
    }
   
    int ans=-1;
    int l=0,r=n*n;
    while (l<=r)
    {
        int mid=(l+r)/2;
        if (check(mid))
        {
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    cout<<ans;
    bool M2;
    cerr<<"-------------------------------------------------"<<endl;
    cerr<<"Time : "<<clock()<<" ms"<<endl;
    cerr<<"Memory : "<<abs(&M2-&M1)/1024/1024<<" MB"<<endl;
    cerr<<"-------------------------------------------------"<<endl;
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100