Submission #888231

#	Time	Username	Problem	Language	Result	Execution time	Memory
888231		ace5	Maze (JOI23_ho_t3)	C++17	86 / 100	2072 ms	584096 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int maxr = 3001;
const int maxc = 6000001;

set<int> r[maxr];
set<short> c[maxc];
vector<short> vis[maxr];
vector<int> d[maxr];
vector<bool> a[maxr];
deque<pair<short,int>> f;

int R,C,n;

int bfs(int si,int sj,int fi,int fj)
{
    for(int i = 0;i < R;++i)
    {
        d[i].resize(C);
        vis[i].resize(C);
        for(int j = 0;j < C;++j)
        {
            d[i][j] = INF;
            vis[i][j] = 0;
            if(i != si || j != sj)
            {
                r[i].insert(j);
                c[j].insert(i);

            }
        }
    }
    d[si][sj] = 0;
    vis[si][sj] = 2;
    f.push_back({si,sj});
    while(f.size())
    {
        int i = f[0].first;
        int j = f[0].second;
        f.pop_front();
       // cout << i << ' ' << j << ' ' << d[fi][fj] << ' ' << vis[5][0] << "\n";
        if(vis[i][j] == 3)
            continue;
        vis[i][j] = 3;
        if(i == fi && j == fj)
            break;
        if(i > 0 && a[i-1][j] == 0 && vis[i-1][j] < 2)
        {
            if(!vis[i-1][j])
            {
                r[i-1].erase(j);
                c[j].erase(i-1);
            }
            vis[i-1][j] = 2;
            d[i-1][j] = d[i][j];
            f.push_front({i-1,j});
        }
        if(j > 0 && a[i][j-1] == 0 && vis[i][j-1] < 2)
        {
            if(!vis[i][j-1])
            {
                r[i].erase(j-1);
                c[j-1].erase(i);
            }
          //  if(i == 5 && j == 1)
         //   {
          //      cout << d[i][j] << ' ' << d[i][j-1] << "\n";
          //  }
            vis[i][j-1] = 2;
            d[i][j-1] = d[i][j];
            f.push_front({i,j-1});
        }
        if(i < R-1 && a[i+1][j] == 0 && vis[i+1][j] < 2)
        {
            if(!vis[i+1][j])
            {
                r[i+1].erase(j);
                c[j].erase(i+1);
            }
            vis[i+1][j] = 2;
            d[i+1][j] = d[i][j];
            f.push_front({i+1,j});
        }
        if(j < C-1 && a[i][j+1] == 0 && vis[i][j+1] < 2)
        {
            if(!vis[i][j+1])
            {
                r[i].erase(j+1);
                c[j+1].erase(i);
            }
            vis[i][j+1] = 2;
            d[i][j+1] = d[i][j];
            f.push_front({i,j+1});
        }
        if(abs(i-fi) <= n && abs(j-fj) <= n && !vis[fi][fj])
        {
            r[fi].erase(fj);
            c[fj].erase(fi);
            //cout << i << ' ' << j << ' ' << d[i][j] << "!\n";
            vis[fi][fj] = 1;
            d[fi][fj] = d[i][j]+1;
            f.push_back({fi,fj});
        }
        int indd = min(R-1,i+n);
        int indu = max(0,i-n);
        int indl = max(0,j-n);
        int indr = min(C-1,j+n);
        int indd2 = i+n-1;
        int indu2 = i-n+1;
        int indr2 = j+n-1;
        int indl2 = j-n+1;
        vector<pair<int,int>> err;
        vector<pair<int,int>> erc;
        for(auto it = r[indd].lower_bound(indl2); (it != r[indd].end() && (*it) <= indr2);++it)
        {
            if(it != r[indd].end() && (*it) <= indr2)
            {
                int k = (*it);
                vis[indd][k] = 1;
                //cout << indd << ' ' << k << ' ' << d[i][j] << "!\n";
                d[indd][k] = d[i][j]+1;
                //cout << d[1][0] << ' ';
                f.push_back({indd,k});
                err.push_back({indd,k});
                c[(*it)].erase(indd);
            }
            else
                break;
        }
        for(auto it = r[indu].lower_bound(indl2); (it != r[indu].end() && (*it) <= indr2);++it)
        {
            if(it != r[indu].end() && (*it) <= indr2)
            {
                int k = (*it);
                vis[indu][k] = 1;
                //cout << indd << ' ' << k << ' ' << d[i][j] << "!\n";
                d[indu][k] = d[i][j]+1;
                //cout << d[1][0] << ' ';
                f.push_back({indu,k});
                err.push_back({indu,k});
                c[(*it)].erase(indu);
            }
            else
                break;
        }
        for(auto it = c[indl].lower_bound(indu2);it != c[indl].end() && (*it) <= indd2;++it)
        {
            if(it != c[indl].end() && (*it) <= indd2)
            {
                int k = (*it);
                vis[k][indl] = 1;
                d[k][indl] = d[i][j]+1;
                //cout << k << ' ' << indl << "!!!\n";
                f.push_back({k,indl});
                erc.push_back({k,indl});
                r[(*it)].erase(indl);
            }
            else
                break;
        }
        for(auto it = c[indr].lower_bound(indu2);it != c[indr].end() && (*it) <= indd2;++it)
        {
            if(it != c[indr].end() && (*it) <= indd2)
            {
                int k = (*it);
                vis[k][indr] = 1;
                d[k][indr] = d[i][j]+1;
                //cout << k << ' ' << indl << "!!!\n";
                f.push_back({k,indr});
                erc.push_back({k,indr});
                r[(*it)].erase(indr);
            }
            else
                break;
        }
        for(auto x : err)
        {
            r[x.first].erase(x.second);
        }
        for(auto x : erc)
        {
            c[x.second].erase(x.first);
        }
    }
    return d[fi][fj];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> R >> C >> n;
    int si,sj,fi,fj;
    cin >> si >> sj >> fi >> fj;
    si--;
    sj--;
    fi--;
    fj--;
    for(int i = 0;i < R;++i)
    {
        string s;
        cin >> s;
        a[i].resize(C);
        for(int j =0;j < C;++j)
        {
            a[i][j] = (s[j] == '.' ? 0 : 1);
        }
    }
    cout << bfs(si,sj,fi,fj);
    return 0;

}

• 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: 0 / 8
• Subtask 8: 0 / 6