Submission #1072724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072724		jer033	Toy (CEOI24_toy)	C++17	100 / 100	536 ms	197832 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int main()
{
    std::ios_base::sync_with_stdio(false);
    int W, H, K, L;
    cin >> W >> H >> K >> L;
    int xh, yh, xv, yv;
    cin >> xh >> yh >> xv >> yv;
    int xstart = xv;
    int ystart = yh;
    int xgoal, ygoal;
    xgoal = -1; ygoal = -1;
    //Note: when accessing, you access y, then x
    vector<vector<bool>> has_obstacle(H, vector<bool> (W, 0));
    for (int i=0; i<H; i++)
        for (int j=0; j<W; j++)
        {
            char x;
            cin >> x;
            if (x=='*')
            {
                xgoal = j;
                ygoal = i;
            }
            else if (x=='X')
            {
                has_obstacle[i][j] = 1;
            }
        }
    vector<vector<pii>> hori_blocks(H, vector<pii> (W, {-1, -1}));
    vector<vector<pii>> veri_blocks(H, vector<pii> (W, {-1, -1}));
    for (int i=0; i<H; i++)
    {
        vector<int> blocks;
        blocks.push_back(-1);
        for (int j = 0; j<W; j++)
            if (has_obstacle[i][j])
                blocks.push_back(j);
        blocks.push_back(W);
        int k = blocks.size();
        for (int conti = 0; conti <= (k-2); conti++)
        {
            int lef = blocks[conti];
            int rig = blocks[conti+1];
            for (int memb = lef+1; memb < rig; memb++)
                hori_blocks[i][memb] = {lef, rig};
        }
    }

    for (int j = 0; j<W; j++)
    {
        vector<int> blocks;
        blocks.push_back(-1);
        for (int i=0; i<H; i++)
            if (has_obstacle[i][j])
                blocks.push_back(i);
        blocks.push_back(H);
        int k = blocks.size();
        for (int conti = 0; conti <= (k-2); conti++)
        {
            int up = blocks[conti];
            int dow = blocks[conti+1];
            for (int memb = up+1; memb < dow; memb++)
                veri_blocks[memb][j] = {up, dow};
        }
    }

    vector<vector<bool>> can_be_center(H, vector<bool> (W, 0));
    for (int i = 0; i<H; i++)
        for (int j = 0; j<W; j++)
        {
            if (((hori_blocks[i][j].second - hori_blocks[i][j].first) > K) and ((veri_blocks[i][j].second - veri_blocks[i][j].first) > L))
                can_be_center[i][j] = 1;
        }

    vector<vector<vector<pii>>> edges(H, vector<vector<pii>> (W));

    //making vertical edges
    for (int i = 0; i<(H-1); i++)
        for (int j=0; j<W; j++)
        {
            int i1 = i;
            int i2 = i+1;
            int j1 = j;
            int j2 = j;
            int intersection1 = max(hori_blocks[i1][j1].first, hori_blocks[i2][j2].first);
            int intersection2 = min(hori_blocks[i1][j1].second, hori_blocks[i2][j2].second);
            if (can_be_center[i1][j1] and can_be_center[i2][j2])
                if ((intersection2 - intersection1) > K)
                {
                    edges[i1][j1].push_back({i2, j2});
                    edges[i2][j2].push_back({i1, j1});
                }
        }
    
    //making horizontal edges
    for (int i = 0; i<H; i++)
        for (int j=0; j<(W-1); j++)
        {
            int i1 = i;
            int i2 = i;
            int j1 = j;
            int j2 = j+1;
            int intersection1 = max(veri_blocks[i1][j1].first, veri_blocks[i2][j2].first);
            int intersection2 = min(veri_blocks[i1][j1].second, veri_blocks[i2][j2].second);
            if (can_be_center[i1][j1] and can_be_center[i2][j2])
                if ((intersection2 - intersection1) > L)
                {
                    edges[i1][j1].push_back({i2, j2});
                    edges[i2][j2].push_back({i1, j1});
                }
        }

    vector<vector<bool>> visited(H, vector<bool> (W, 0));
    queue<pii> visitlist;
    visitlist.push({ystart, xstart});
    visited[ystart][xstart] = 1;
    while (!visitlist.empty())
    {
        pii next_square = visitlist.front();
        visitlist.pop();
        int icurr = next_square.first;
        int jcurr = next_square.second;
        for (pii neigh: edges[icurr][jcurr])
        {
            int inex = neigh.first;
            int jnex = neigh.second;
            if (visited[inex][jnex] == 0)
            {
                visited[inex][jnex] = 1;
                visitlist.push({inex, jnex});
            }
        }
    }

    if (visited[ygoal][xgoal] == 1)
        cout << "YES\n";
    else
        cout << "NO\n";
}

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