제출 #500710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
500710		beedle	Mecho (IOI09_mecho)	C++14	100 / 100	630 ms	12020 KiB

mecho

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#define pi 3.141592653589793238
#define ll long long
#define ld long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 998244353ll
#define INF 1000000000000000000
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast                                                                  \
    ios_base::sync_with_stdio (false);                                        \
    cin.tie (NULL);                                                           \
    cout.tie (NULL)

using namespace std;

vector <pair<int,int>> dir={{0,1},{0,-1},{1,0},{-1,0}};

signed main ()
{
    fast;
 
    // freopen("atlarge.in","r",stdin);
    // freopen("atlarge.out","w",stdout);
 
    int n,s;
    cin>>n>>s;

    string g[n];
    rep(i,0,n-1)
    cin>>g[i];

    int lo=0;
    int hi=n*n;
    int best=-1;

    while(lo<=hi)
    {
        int mid=(lo+hi)/2;
        
        queue <pair<int,int>> q;
        int disth[n][n];
        rep(i,0,n-1)
        rep(j,0,n-1)
        disth[i][j]=mod;

        rep(i,0,n-1)
        rep(j,0,n-1)
        if(g[i][j]=='H')
        disth[i][j]=0, q.push({i,j});

        while(!q.empty())
        {
            auto v=q.front();
            q.pop();

            if(disth[v.ff][v.ss]==mid)
            continue;

            for(auto mv:dir)
            {
                pair <int,int> u={v.ff+mv.ff,v.ss+mv.ss};
                if(u.ff>=0 && u.ff<n && u.ss>=0 && u.ss<n)
                if(g[u.ff][u.ss]=='G' || g[u.ff][u.ss]=='M')
                if(disth[u.ff][u.ss]>disth[v.ff][v.ss]+1)
                {
                    disth[u.ff][u.ss]=disth[v.ff][v.ss]+1;
                    q.push(u);
                }
            }
        }

        rep(i,0,n-1)
        rep(j,0,n-1)
        if(disth[i][j]!=mod)
        {
            disth[i][j]=0;
            q.push({i,j});
        }
        
        while(!q.empty())
        {
            auto v=q.front();
            q.pop();

            for(auto mv:dir)
            {
                pair <int,int> u={v.ff+mv.ff,v.ss+mv.ss};
                if(u.ff>=0 && u.ff<n && u.ss>=0 && u.ss<n)
                if(g[u.ff][u.ss]=='G' || g[u.ff][u.ss]=='M')
                if(disth[u.ff][u.ss]>disth[v.ff][v.ss]+1)
                {
                    disth[u.ff][u.ss]=disth[v.ff][v.ss]+1;
                    q.push(u);
                }
            }
        }

        // rep(i,0,n-1)
        // {
        //     rep(j,0,n-1)
        //     {
        //         if(disth[i][j]==mod)
        //         cout<<"-";
        //         else
        //         cout<<disth[i][j];
        //     }
        //     cout<<endl;
        // }

        // cout<<endl;

        int distm[n][n];
        rep(i,0,n-1)
        rep(j,0,n-1)
        distm[i][j]=mod;

        pair <int,int> start;
        rep(i,0,n-1)
        rep(j,0,n-1)
        if(g[i][j]=='M')
        start={i,j};

        distm[start.ff][start.ss]=0;
        if(disth[start.ff][start.ss]!=0)
        q.push(start);

        while(!q.empty())
        {
            auto v=q.front();
            q.pop();

            for(auto mv:dir)
            {
                pair <int,int> u={v.ff+mv.ff,v.ss+mv.ss};
                if(u.ff>=0 && u.ff<n && u.ss>=0 && u.ss<n)
                if(g[u.ff][u.ss]=='G' || g[u.ff][u.ss]=='M' || g[u.ff][u.ss]=='D')
                if(distm[u.ff][u.ss]>distm[v.ff][v.ss]+1)
                {
                    if((distm[v.ff][v.ss]+1)/s<disth[u.ff][u.ss])
                    {
                        distm[u.ff][u.ss]=distm[v.ff][v.ss]+1;
                        q.push(u);
                    }
                }
            }
        }

        // rep(i,0,n-1)
        // {
        //     rep(j,0,n-1)
        //     {
        //         if(distm[i][j]==mod)
        //         cout<<"-";
        //         else
        //         cout<<distm[i][j];
        //     }
        //     cout<<endl;
        // }

        // cout<<endl;

        // bool cango[n][n], visited[n][n];
        // rep(i,0,n-1)
        // rep(j,0,n-1)
        // {
        //     if(distm[i][j]/s<disth[i][j] && g[i][j]!='T')
        //     cango[i][j]=true;
        //     else
        //     cango[i][j]=false;

        //     visited[i][j]=false;
        // }

        // if(cango[start.ff][start.ss])
        // q.push(start), visited[start.ff][start.ss]=true;

        // rep(i,0,n-1)
        // {
        //     rep(j,0,n-1)
        //     {
        //         if(cango[i][j])
        //         cout<<"+";
        //         else
        //         cout<<"-";
        //     }
        //     cout<<endl;
        // }

        // cout<<endl;

        // while(!q.empty())
        // {
        //     auto v=q.front();
        //     q.pop();

        //     for(auto mv:dir)
        //     {
        //         pair <int,int> u={v.ff+mv.ff,v.ss+mv.ss};
        //         if(u.ff>=0 && u.ff<n && u.ss>=0 && u.ss<n)
        //         if(cango[u.ff][u.ss])
        //         if(!visited[u.ff][u.ss])
        //         {
        //             visited[u.ff][u.ss]=true;
        //             q.push(u);
        //         }
        //     }
        // }

        bool ok=false;
        rep(i,0,n-1)
        rep(j,0,n-1)
        if(g[i][j]=='D')
        if(distm[i][j]!=mod)
        ok=true;

        if(ok)
        {
            best=mid;
            lo=mid+1;
        }
        else
        {
            hi=mid-1;
        }
    }

    cout<<best;

    return 0;
}

/*
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT
*/

• Subtask 1: 100 / 100