Submission #697002

#	Time	Username	Problem	Language	Result	Execution time	Memory
697002		MarwenElarbi	Mecho (IOI09_mecho)	C++14	30 / 100	156 ms	6920 KiB

mecho

#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define onbit __builtin_popcount
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
using namespace std;
const int MOD = 1e9+7;
const int nax = 805;
const int MAX_VAL = 1e6;
double PI=3.14159265359;
int arx[8]={1,1,0,-1,-1,-1, 0, 1};
int ary[8]={0,1,1, 1, 0,-1,-1,-1};
typedef complex<int> Point;
#define X real()
#define Y imag()
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
char tab[nax][nax];
int dis[nax][nax];
int n,k;
bool test;
int vis[nax][nax];
pair<int,int> last;
bool inside(int x,int y)
{
    return (x>=0&&x<n&&y>=0&&y<n&&tab[x][y]!='T'&&tab[x][y]!='D');
}
bool mecho(int x,int y)
{
    return (x>=0&&x<n&&y>=0&&y<n&&tab[x][y]!='T'&&tab[x][y]!='H');
}
void dfs(int sum)
{
    queue<pair<pair<int,int>,int>> dq;
    dq.push({{last.fi,last.se},0});
    vis[last.fi][last.se]=sum;
    while(!dq.empty())
    {
        int x=dq.front().fi.fi;
        int y=dq.front().fi.se;
        int z=dq.front().se;
        dq.pop();
        for(int i=0;i<7;i+=2)
        {
            int a=x+arx[i];
            int b=y+ary[i];
            int c=0;
            c+= (z==k);
            int p=z;
            if (p==k) p=0;
            if (!mecho(a,b)) continue;
            if (vis[a][b]!=-1) continue;
            if (dis[a][b]<=c+vis[x][y]&&dis[a][b]!=-1) continue;
            if (tab[a][b]=='D'){
                /*cout << "nabba"<<endl;
                for (int i = 0; i < n; ++i)
                {
                    for (int j = 0; j < n; ++j)
                    {
                        cout << vis[i][j]<<" ";
                    }cout<< endl;
                }*/
                test=true;
                return;
            }
            vis[a][b]=vis[x][y]+c;
            dq.push({{a,b},p+1});
        }
    }
    /*for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cout << vis[i][j]<<" ";
        }cout<< endl;
    }*/

}
int main(){
    optimise;
    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    //setIO("atlarge");
    cin>>n>>k;
    memset(dis,-1,sizeof dis);
    queue<pair<int,int>> q;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin>>tab[i][j];
            if (tab[i][j]=='H'){
                q.push({i,j});
                dis[i][j]=0;
            }
            if (tab[i][j]=='M'){
                last.fi=i;
                last.se=j;
            }
        }
    }
    while(!q.empty())
    {
        int x=q.front().fi;
        int y=q.front().se;
        q.pop();
        for(int i=0;i<7;i+=2)
        {
            int a=x+arx[i];
            int b=y+ary[i];
            if (!inside(a,b)) continue;
            if (dis[a][b]!=-1) continue;
            dis[a][b]=dis[x][y]+1;
            q.push({a,b});
        }
    }
    /*for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cout << dis[i][j]<<" ";
        }cout << endl;
    }*/
    int l=0;
    int r=1e6;
    while(r-l>1){
        int mid=(r+l)/2;
        //if (mid<10) cout << mid<<endl;
        memset(vis,-1,sizeof vis);
        test=false;
        dfs(mid);
        if(test) l=mid;
        else r=mid;

    }
    if (l<=0){
        cout <<-1<<endl;
    }else cout << l<<endl;
}   

Compilation message (stderr)

mecho.cpp: In function 'void setIO(std::string)':
mecho.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 100