Submission #1289171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289171		quangminh412	Toy (CEOI24_toy)	C++17	100 / 100	373 ms	170060 KiB

Main

/*
  Ben Watson

  Quang Minh MasterDDDDD
*/

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const string name = "test";

void solve();
signed main()
{
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

// main program
const int maxn = 1501;
const int maxN = maxn * maxn;

vector<int> adj[maxN];
int rows_l[maxn][maxn], cols_u[maxn][maxn];
int rows_r[maxn][maxn], cols_d[maxn][maxn];
char a[maxn][maxn];
int w, h, k, l, xh, yh, xv, yv, Tx, Ty;

bool isin(int x, int y) { return 1 <= min(x, y) && x <= h && y <= w && a[x][y] == '.'; }
int id(int x, int y) { return (x - 1) * w + y; }

void build()
{
    for (int i = 1; i <= h; i++)
    {
        int last = 0;
        for (int j = 1; j <= w; j++)
            if (a[i][j] == '.')
                rows_l[i][j] += ++last;
            else
                rows_l[i][j] = last = 0;
        last = 0;
        for (int j = w; j > 0; j--)
            if (a[i][j] == '.')
                rows_r[i][j] += ++last;
            else
                rows_r[i][j] = last = 0;
    }
    for (int j = 1; j <= w; j++)
    {
        int last = 0;
        for (int i = 1; i <= h; i++)
            if (a[i][j] == '.')
                cols_u[i][j] += ++last;
            else
                cols_u[i][j] = last = 0;
        last = 0;
        for (int i = h; i > 0; i--)
            if (a[i][j] == '.')
                cols_d[i][j] += ++last;
            else
                cols_d[i][j] = last = 0;
    }
    for (int x = 1; x <= h; x++)
        for (int y = 1; y <= w; y++)
        {
            if (!isin(x, y))
                continue;
            int cur = id(x, y);
            if (rows_l[x][y] + rows_r[x][y] - 1 >= k)
            {
                if (isin(x, y + 1))
                {
                    int U = min(cols_u[x][y], cols_u[x][y + 1]);
                    int D = min(cols_d[x][y], cols_d[x][y + 1]);
                    if (U + D - 1 >= l)
                        adj[cur].push_back(id(x, y + 1));
                }
                if (isin(x, y - 1))
                {
                    int U = min(cols_u[x][y], cols_u[x][y - 1]);
                    int D = min(cols_d[x][y], cols_d[x][y - 1]);
                    if (U + D - 1 >= l)
                        adj[cur].push_back(id(x, y - 1));
                }
            }
            if (cols_u[x][y] + cols_d[x][y] - 1 >= l)
            {
                if (isin(x - 1, y))
                {
                    int L = min(rows_l[x][y], rows_l[x - 1][y]);
                    int R = min(rows_r[x][y], rows_r[x - 1][y]);
                    if (L + R - 1 >= k)
                        adj[cur].push_back(id(x - 1, y));
                }
                if (isin(x + 1, y))
                {
                    int L = min(rows_l[x][y], rows_l[x + 1][y]);
                    int R = min(rows_r[x][y], rows_r[x + 1][y]);
                    if (L + R - 1 >= k)
                        adj[cur].push_back(id(x + 1, y));
                }
            }
        }
}

void solve()
{
    cin >> w >> h >> k >> l;
    cin >> xh >> yh >> xv >> yv;
    xh++; yh++; xv++; yv++;
    swap(xh, yh); swap(xv, yv);
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
        {
            cin >> a[i][j];
            if (a[i][j] == '*')
            {
                Tx = i;
                Ty = j;
                a[i][j] = '.';
            }
        }

    build();

    vector<int> visited(h * w + 1, 0);
    int S = id(xh, yv);
    queue<int> q;
    q.push(S);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();

        visited[u] = 1;
        for (int v : adj[u])
        {
            if (visited[v])
                continue;
            visited[v] = 1;
            q.push(v);
        }
    }

    cout << (visited[id(Tx, Ty)] == 1 ? "YES\n" : "NO\n");
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27