Submission #895977

#	Time	Username	Problem	Language	Result	Execution time	Memory
895977		niter	Maze (JOI23_ho_t3)	C++14	51 / 100	2067 ms	34340 KiB

Main

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define pb push_back
#define ins insert
#define pii pair<int,int>
#define ff first
#define ss second
#define BAE(x) (x).begin(), (x).end()
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define spac cerr << ' ';
#define entr cerr << endl;
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
using namespace std;
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
ostream& operator<<(ostream& os, pii A){ os << "\n[" << A.ff << ", " << A.ss << "]"; }

inline bool check(int i, int j, int n, int m){
    return i >= 0 && j >= 0 && i < n && j < m;
}
const int INF = (int)(1e9);
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
vector<pii> dr;
vector<vector<char>> c;
vector<vector<int>> dis;
vector<vector<bool>> special;

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m, L;
    cin >> n >> m >> L;
    pii s, t;
    cin >> s.ff >> s.ss >> t.ff >> t.ss;
    s.ff--; s.ss--; t.ff--; t.ss--;
    c = vector<vector<char>>(n, vector<char>(m, ' '));
    loop(i,0,n){
        loop(j,0,m){
            cin >> c[i][j];
        }
    }
    for(int i = -1; i <= 1; i += 2){
        for(int j = -1; j <= 1; j += 2){
            for(int k = 0; k < L; k ++){
                dr.pb({k * i, L * j});
                dr.pb({L * j, k * i});
            }
        }
    }
    sort(BAE(dr));
    dr.resize(unique(BAE(dr)) - dr.begin());
//    STL(dr);
    special = vector<vector<bool>>(n, vector<bool>(m, false));
    for(auto &i:dr){
        int nx = s.ff + i.ff;
        int ny = s.ss + i.ss;
        if(check(nx, ny, n, m)){
            special[nx][ny] = true;
        }
    }
    dis = vector<vector<int>>(n, vector<int>(m, INF));
    dis[s.ff][s.ss] = 0;
    queue<pii> Q;
    Q.push(s);
    while(!Q.empty()){
        int nowx = Q.front().ff;
        int nowy = Q.front().ss;
        Q.pop();
        if(special[nowx][nowy]) continue;
        loop(d,0,4){
            int nx = nowx + dx[d];
            int ny = nowy + dy[d];
            if(!check(nx, ny, n, m)) continue;
            if(dis[nx][ny] == INF){
                dis[nx][ny] = 1;
                Q.push({nx, ny});
            }
        }
    }
//    for(auto &i:dis){
//        STL(i) entr
//    }
    priority_queue<pair<int,pii>, vector<pair<int,pii>>, greater<pair<int,pii>>> pq;
    loop(i,0,n){
        loop(j,0,m){
            if(dis[i][j] != INF) pq.push({dis[i][j], {i, j}});
        }
    }
//    pq.push({0, s});
    while(!pq.empty()){
        int nowx = pq.top().ss.ff;
        int nowy = pq.top().ss.ss;
        int nowd = pq.top().ff;
        pq.pop();
        if(nowd != dis[nowx][nowy]) continue;
        loop(d,0,4){
            int nx = nowx + dx[d];
            int ny = nowy + dy[d];
            if(!check(nx, ny, n, m)) continue;
            if(c[nx][ny] == '#') continue;
            if(dis[nx][ny] > nowd){
                dis[nx][ny] = nowd;
                pq.push({dis[nx][ny], {nx, ny}});
            }
        }
        for(auto &d:dr){
            int nx = nowx + d.ff;
            int ny = nowy + d.ss;
            if(!check(nx, ny, n, m)) continue;
            if(dis[nx][ny] > nowd + 1){
                dis[nx][ny] = nowd + 1;
                pq.push({dis[nx][ny], {nx, ny}});
            }
        }
    }
    assert(dis[t.ff][t.ss] != INF);
    cout << dis[t.ff][t.ss] << '\n';
}
/*
5 5 2
1 1
4 4
.####
#####
#####
###.#
#####
*/

Compilation message (stderr)

Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::pair<int, int>)':
Main.cpp:17:86: warning: no return statement in function returning non-void [-Wreturn-type]
   17 | ostream& operator<<(ostream& os, pii A){ os << "\n[" << A.ff << ", " << A.ss << "]"; }
      |                                                                                      ^

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