Submission #1045753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045753		CyberCow	Toy (CEOI24_toy)	C++17	100 / 100	92 ms	53088 KiB

Main

#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((x).size())
typedef long long ll;
using ull = unsigned long long;
using namespace std;
mt19937 rnd(348502);
ll mod1 = 998244353;
ll mod = 1e9 + 7;
const ll N = 1505;

int a[N][N];
int achdzax[N][N];
int achdzax1[N][N];
int verevnerqev[N][N];
int verevnerqev1[N][N];
int color[N][N];

void solve()
{
    int n, i, j, m, x, y, c, skx = -1, sky = -1, vrx = -1, vry = -1, k, l;
    cin >> m >> n >> k >> l;
    int xh, yh, xv, yv;
    cin >> xh >> yh >> xv >> yv;
    for ( i = 1; i <= n; i++)
    {
        for ( j = 1; j <= m; j++)
        {
            char c;
            cin >> c;
            if (c == '*')
            {
                vrx = i;
                vry = j;
            }
            else if(c == 'X')
            {
                a[i][j] = 1;
            }
        }
    }
    for ( i = 1; i <= n; i++)
    {
        int qan = 0;
        for ( j = 1; j <= m; j++)
        {
            if (a[i][j] == 1)
                qan = 0;
            else
                qan++;
            achdzax[i][j] += qan;
        }
        qan = 0;
        for ( j = m; j >= 1; j--)
        {
            if (a[i][j] == 1)
            {
                qan = 0;
            }
            else
            {
                qan++;
            }
            achdzax1[i][j] += qan;
        }
    }
    for ( j = 1; j <= m; j++)
    {
        int qan = 0;
        for ( i = 1; i <= n; i++)
        {
            if (a[i][j] == 1)
            {
                qan = 0;
            }
            else
            {
                qan++;
            }
            verevnerqev[i][j] += qan;
        }
        qan = 0;
        for (i = n; i >= 1; i--)
        {
            if (a[i][j] == 1)
            {
                qan = 0;
            }
            else
            {
                qan++;
            }
            verevnerqev1[i][j] += qan;
        }
    }
    for ( i = 0; i <= n + 1; i++)
    {
        a[i][0] = 1;
        a[i][m + 1] = 1;
    }
    for ( i = 0; i <= m + 1; i++)
    {
        a[0][i] = 1;
        a[n + 1][i] = 1;
    }
    queue<pair<int, int>> q;
    skx = yh;
    sky = xv;
    q.push({ skx + 1, sky + 1 });
    while (!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        color[x][y] = 1;
        q.pop();
        if (min(achdzax[x - 1][y], achdzax[x][y]) + min(achdzax1[x - 1][y], achdzax1[x][y]) - 1 >= k && color[x - 1][y] == 0)
        {
            q.push({ x - 1, y });
            color[x - 1][y] = 1;
        }
        if (min(achdzax[x + 1][y], achdzax[x][y]) + min(achdzax1[x + 1][y], achdzax1[x][y]) - 1 >= k && color[x + 1][y] == 0)
        {
            q.push({ x + 1, y });
            color[x + 1][y] = 1;
        }
        if (min(verevnerqev[x][y - 1], verevnerqev[x][y]) + min(verevnerqev1[x][y - 1], verevnerqev1[x][y]) - 1 >= l && color[x][y - 1] == 0)
        {
            q.push({ x, y - 1 });
            color[x][y - 1] = 1;
        }
        if (min(verevnerqev[x][y + 1], verevnerqev[x][y]) + min(verevnerqev1[x][y + 1], verevnerqev1[x][y]) - 1 >= l && color[x][y + 1] == 0)
        {
            q.push({ x, y + 1 });
            color[x][y + 1] = 1;
        }
    }
    if (color[vrx][vry] == 1)
    {
        cout << "YES\n";
    }
    else
    {
        cout << "NO\n";
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:40:27: warning: unused variable 'c' [-Wunused-variable]
   40 |     int n, i, j, m, x, y, c, skx = -1, sky = -1, vrx = -1, vry = -1, k, l;
      |                           ^

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