oj.uz

Submission #1045734

# Submission time Handle Problem Language Result Execution time Memory
1045734 2024-08-06T07:17:43 Z CyberCow Toy (CEOI24_toy) C++17
0 / 100
 1500 ms 803252 KB 
#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 verevnerqev[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++;
            }
            achdzax[i][j] += max(0, qan - 1);
        }
    }
    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++;
            }
            verevnerqev[i][j] += max(0, qan - 1);
        }
    }
    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]) >= k && color[x - 1][y] == 0)
        {
            q.push({ x - 1, y });
        }
        if (min(achdzax[x + 1][y], achdzax[x][y]) >= k && color[x + 1][y] == 0)
        {
            q.push({ x + 1, y });
        }
        if (min(verevnerqev[x][y - 1], verevnerqev[x][y]) >= l && color[x][y - 1] == 0)
        {
            q.push({ x, y - 1 });
        }
        if (min(verevnerqev[x][y + 1], verevnerqev[x][y]) >= l && color[x][y + 1] == 0)
        {
            q.push({ x, y + 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

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

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 0 ms 6492 KB Output is correct

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 0 ms 6492 KB Output is correct
3 Correct 1427 ms 244940 KB Output is correct
4 Execution timed out 1615 ms 802612 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 0 ms 6492 KB Output is correct
3 Correct 1427 ms 244940 KB Output is correct
4 Execution timed out 1615 ms 802612 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 0 ms 6492 KB Output is correct
3 Execution timed out 1533 ms 803252 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 0 ms 6492 KB Output is correct
3 Correct 1427 ms 244940 KB Output is correct
4 Execution timed out 1615 ms 802612 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 0 ms 6492 KB Output is correct
3 Correct 1427 ms 244940 KB Output is correct
4 Execution timed out 1615 ms 802612 KB Time limit exceeded
5 Halted 0 ms 0 KB -