Submission #767060

#	Time	Username	Problem	Language	Result	Execution time	Memory
767060		sysia	Maze (JOI23_ho_t3)	C++17	86 / 100	2078 ms	957212 KiB

Main

//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
 
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
typedef pair<int, int> T;
const int oo = 1e9+7;
const int mx = 2455;
 
void solve(){
    int n, m, k; scanf("%d %d %d", &n, &m, &k);
    T s, e;
    scanf("%d %d", &s.first, &s.second);
    scanf("%d %d", &e.first, &e.second);
    vector a(n+1, vector<char>(m+1));
    function<char()> daj = [&]() {
        char c = getchar_unlocked();
        if (c == ' ' || c == '\n') return (char)getchar_unlocked();
        return c;
    };
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            a[i][j] = daj();
        }
    }
    auto in = [&](T ss){
        return ss.first < 1 || ss.second < 1 || ss.first > n || ss.second > m;
    };
    vector<T>q, q2;
    vector<bitset<mx>>tab(m+1);
    for (int j = 1; j<=m; j++){
        tab[j].set();
    }
    const vector<int>X = {-1, 1, 0, 0};
    const vector<int>Y = {0, 0, -1, 1};
    vector dist(n+1, vector<int>(m+1, oo));
    dist[s.first][s.second] = 0;
    q.emplace_back(s);
    tab[s.second].set(s.first, 0);
    while (1){
        for (int i = 0; i<(int)q.size(); i++){
            auto v = q[i];
            debug(v);
            for (int ck = 0; ck < 4; ck++){
                T x = {v.first + X[ck], v.second + Y[ck]};
                if (in(x)) continue;
                if (a[x.first][x.second] == '.'){
                    if (dist[x.first][x.second] == oo){
                        dist[x.first][x.second] = dist[v.first][v.second];
                        if (x == e) {
                            printf("%d\n", dist[e.first][e.second]);
                            exit(0);
                        }
                        tab[x.second][x.first] = 0;
                        q.emplace_back(x);
                    }
                } 
            }
            q2.emplace_back(v);
        }
        q.clear();
        for (int j = 0; j<(int)q2.size(); j++){
            auto v = q2[j];
            debug(v);
            for (int i = max(1, v.second - k); i<=min(m, v.second+k); i++){
                int from = (i == v.second - k || i == v.second + k ? max(1, v.first-k+1) : max(1, v.first-k));
                int to = (i == v.second - k || i == v.second + k ? min(n, v.first+k-1) : min(n, v.first+k));
                for (int now = tab[i]._Find_next(from-1); now <= to; now = tab[i]._Find_next(now)){
                    dist[now][i] = dist[v.first][v.second]+1;
                    if (T{now, i} == e) {
                        printf("%d\n", dist[e.first][e.second]);
                        exit(0);
                    }
                    tab[i][now] = 0;
                    if (i == v.second - k || i == v.second + k || now == v.first-k || now == v.first+k) q.emplace_back(now, i);
                }
            }
        }
        q2.clear();
    }
    // for (int i = 1; i<=n; i++){
    //     for (int j = 1; j<=m; j++){
    //         cerr << dist[i][j] << " ";
    //     }
    //     cerr << "\n";
    // }
    printf("%d\n", dist[e.first][e.second]);
}
 
int32_t main(){
    solve();
 
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:33:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     int n, m, k; scanf("%d %d %d", &n, &m, &k);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d %d", &s.first, &s.second);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d %d", &e.first, &e.second);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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