Submission #763579

#	Time	Username	Problem	Language	Result	Execution time	Memory
763579		caganyanmaz	Maze (JOI23_ho_t3)	C++17	100 / 100	980 ms	306776 KiB

Main

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

constexpr static int MAX_R = 2500;


int r, c, n;
vector<int> min_dist[MAX_R];
vector<vector<array<int, 2>>> steps;
vector<bool> white[MAX_R];
vector<bool> visited[MAX_R];
vector<bool> seen[MAX_R];


void clean_dfs(int x, int y, int step);

void clean_check(int x, int y, int step)
{
        if (c > x && x >= 0 && r > y && y >= 0 && !visited[y][x] && white[y][x])
                clean_dfs(x, y, step);
}

void clean_dfs(int x, int y, int step)
{
        visited[y][x] = true;
        min_dist[y][x] = step;
        if (!seen[y][x])
                steps[step].pb({x, y});
        clean_check(x-1, y, step);
        clean_check(x+1, y, step);
        clean_check(x, y-1, step);
        clean_check(x, y+1, step);
}

vector<int> bvert[MAX_R];
vector<int> bhrz[MAX_R];
void bfs(int step)
{
        queue<array<int, 2>> vq, hq;
        for (array<int, 2> pos : steps[step])
                vq.push(pos);
        while (vq.size())
        {
                auto [x, y] = vq.front();
                vq.pop();
                if (min_dist[y][x] == step)
                        bvert[y][x] = 0;
                for (int dy = -1; dy <= 1; dy+=2)
                {
                        if (r > y+dy && y+dy >= 0 && !visited[y+dy][x] && !seen[y+dy][x])
                        {
                                seen[y+dy][x] = true;
                                min_dist[y+dy][x] = step + 1;
                                steps[step+1].pb({x, y+dy});
                                bvert[y+dy][x] = bvert[y][x]+1;
                                if (bvert[y+dy][x] < n)
                                        vq.push({x, y+dy});
                        }
                }
        }
        vector<array<int, 2>> lasts;
        for (array<int, 2> pos : steps[step])
                hq.push(pos);
        for (array<int, 2> pos : steps[step+1])
                if (bvert[pos[1]][pos[0]] < n)
                        hq.push(pos);
                else
                        lasts.push_back(pos);
        if (n > 1)
                for (array<int, 2> pos : lasts)
                        hq.push(pos);
        while (hq.size())
        {
                auto [x, y] = hq.front();
                hq.pop();
                if (bvert[y][x] != -1 && bvert[y][x] < n)
                        bhrz[y][x] = 0;
                else if (bvert[y][x] != -1 && bvert[y][x] == n)
                        bhrz[y][x] = 1;
                for (int dx = -1; dx <= 1; dx+=2)
                {
                        if (c > x+dx && x+dx >= 0 && !visited[y][x+dx] && !seen[y][x+dx])
                        {
                                seen[y][x+dx] = true;
                                min_dist[y][x+dx] = step + 1;
                                steps[step+1].pb({x+dx, y});
                                bhrz[y][x+dx] = bhrz[y][x]+1;
                                if (bhrz[y][x+dx] < n)
                                        hq.push({x+dx, y});
                        }
                }
        }
}



int main()
{
        cin >> r >> c >> n;
        int sx, sy, ex, ey;
        cin >> sy >> sx;
        cin >> ey >> ex;
        sy--, sx--, ey--, ex--;
        for (int y = 0; y < r; y++)
        {
                string s;
                white[y] = vector<bool>(c);
                visited[y] = vector<bool>(c);
                min_dist[y] = vector<int>(c);
                bvert[y] = vector<int>(c, -1);
                bhrz[y] = vector<int>(c, -1);
                seen[y] = vector<bool>(c, false);
                cin >> s;
                for (int x = 0; x < c; x++)
                        white[y][x] = s[x] == '.';
        }
        steps.pb(vector<array<int, 2>>(0));
        int current_step = 0;
        clean_dfs(sx, sy, 0);
        for (auto [x, y] : steps[current_step])
        while (!visited[ey][ex] && !seen[ey][ex])
        {
                steps.pb(vector<array<int, 2>>(0));
                bfs(current_step);
                current_step++;
                for (int i = steps[current_step].size()-1; i >= 0; i--)
                {
                        auto [x, y] = steps[current_step][i];
                        if (!visited[y][x])
                                clean_dfs(x, y, current_step);
                }
        }
        cout << min_dist[ey][ex] << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:121:19: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  121 |         for (auto [x, y] : steps[current_step])
      |                   ^~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 8 / 8
• Subtask 8: 6 / 6