제출 #919760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
919760		Flan312	Mecho (IOI09_mecho)	C++17	84 / 100	163 ms	3928 KiB

mecho

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task ""
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int, int>
using namespace std;
const int nmax = 802;
const int mvx[] = {1, -1, 0, 0};
const int mvy[] = {0, 0, 1, -1};
int n, s;
char a[nmax][nmax];
pii Start;
int reach_time[nmax][nmax];
void Bee_timetable()
{
    queue <pii> q;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (a[i][j] == 'H')
            {
                reach_time[i][j] = 0;
                q.emplace(i, j);
            }
    while(q.size())
    {
        auto [u, v] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k)
        {
            int x = u + mvx[k];
            int y = v + mvy[k];
            if (x < 1 || x > n) continue;
            if (y < 1 || y > n) continue;
            if (a[x][y] == 'D' || a[x][y] == 'T') continue;
            if (reach_time[x][y] != 1e9) continue;
            reach_time[x][y] = reach_time[u][v] + 1;
            q.emplace(x, y);
        }
    }
}
bool check(int mid)
{
    queue <tii> q;
    q.emplace(Start.fi, Start.se, mid, s);
    vector <vector<bool> > vs(n + 2, vector <bool> (n + 2, 0));
    while(q.size())
    {
        auto [u, v, time, rem_step] = q.front();
        q.pop();
        if (a[u][v] == 'D') return 1;
        if (!rem_step) rem_step = s, ++time;
        if (reach_time[u][v] <= time) continue;
        for (int k = 0; k < 4; ++k)
        {
            int x = u + mvx[k];
            int y = v + mvy[k];
            if (x < 1 || x > n) continue;
            if (y < 1 || y > n) continue;
            if (vs[x][y]) continue;
            if (a[x][y] == 'T') continue;
            vs[x][y] = 1;
            q.emplace(x, y, time, rem_step - 1);
        }
    }
    return 0;
}
int main()
{
    if (ifstream(task".inp")) nx
    fast
    cin >> n >> s;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            cin >> a[i][j];
            reach_time[i][j] = 1e9;
            if (a[i][j] == 'M') Start = {i, j};
        }
    Bee_timetable();
    int l = 0, r = n * n, ans = 0;
    while(l <= r)
    {
        int mid = l + r >> 1;
        if (check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << ans;
}

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

mecho.cpp: In function 'int main()':
mecho.cpp:89:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |         int mid = l + r >> 1;
      |                   ~~^~~
mecho.cpp:7:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:75:31: note: in expansion of macro 'nx'
   75 |     if (ifstream(task".inp")) nx
      |                               ^~
mecho.cpp:7:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:75:31: note: in expansion of macro 'nx'
   75 |     if (ifstream(task".inp")) nx
      |                               ^~

• Subtask 1: 84 / 100