Submission #1046856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046856		1L1YA	Maze (JOI23_ho_t3)	C++17	100 / 100	380 ms	479892 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv
 
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll N = 6e6 + 50;
const ll Mod = 1e9 + 7;
 
int R, C, n; 
pii s, t;
 
string a[N];
 
struct cst{
    int F = Mod, S, T;
};
 
vector<cst> cost[N];
 
bool ok(int x, int y){
    return (0 <= min(x, y) && x < R && y < C);
}
 
int main(){
    fast_io;
    
    cin >> R >> C >> n >> s.F >> s.S >> t.F >> t.S;
    s.F--; s.S--; t.F--; t.S--; n--; n = -n;
 
    for(int i = 0; i < R; i++) cin >> a[i];
    for(int i = 0; i < R; i++) cost[i].resize(C);
 
    vector<pii> q0, q1;
 
    q0.pb({s.F, s.S});
    cost[s.F][s.S] = {0, 0, 0};
 
    while(!q0.empty()){
        for(int i = 0; i < q0.size(); i++){
            auto [r, c] = q0[i];
            auto [x, y, z] = cost[r][c];
            if(y != 0){
                if(ok(r+1, c) && x < cost[r+1][c].F){
                    cost[r+1][c] = {x, y+1, z};
                    q0.pb({r+1, c});
                }
                if(ok(r-1, c) && x < cost[r-1][c].F){
                    cost[r-1][c] = {x, y+1, z};
                    q0.pb({r-1, c});
                }
            }
        }
        for(int i = 0; i < q0.size(); i++){
            auto [r, c] = q0[i];
            auto [x, y, z] = cost[r][c];
            if(z != 0){
                if(ok(r, c+1) && x < cost[r][c+1].F){
                    cost[r][c+1] = {x, y, z+1};
                    q0.pb({r, c+1});
                }
                if(ok(r, c-1) && x < cost[r][c-1].F){
                    cost[r][c-1] = {x, y, z+1};
                    q0.pb({r, c-1});
                }
            }
        }
        for(int i = 0; i < q0.size(); i++){
            auto [r, c] = q0[i];
            auto [x, y, z] = cost[r][c];
            if(ok(r+1, c)){
                if(a[r+1][c] == '#'){
                    if(cost[r+1][c].F > x+1){
                        cost[r+1][c] = {x+1, n, n};
                        q1.pb({r+1, c});
                    }
                }
                else{
                    if(cost[r+1][c].F > x){
                        cost[r+1][c] = {x, 0, 0};
                        q0.pb({r+1, c});
                    }
                }
            }
            if(ok(r-1, c)){
                if(a[r-1][c] == '#'){
                    if(cost[r-1][c].F > x+1){
                        cost[r-1][c] = {x+1, n, n};
                        q1.pb({r-1, c});
                    }
                }
                else{
                    if(cost[r-1][c].F > x){
                        cost[r-1][c] = {x, 0, 0};
                        q0.pb({r-1, c});
                    }
                }
            }
            if(ok(r, c+1)){
                if(a[r][c+1] == '#'){
                    if(cost[r][c+1].F > x+1){
                        cost[r][c+1] = {x+1, n, n};
                        q1.pb({r, c+1});
                    }
                }
                else{
                    if(cost[r][c+1].F > x){
                        cost[r][c+1] = {x, 0, 0};
                        q0.pb({r, c+1});
                    }
                }
            }
            if(ok(r, c-1)){
                if(a[r][c-1] == '#'){
                    if(cost[r][c-1].F > x+1){
                        cost[r][c-1] = {x+1, n, n};
                        q1.pb({r, c-1});
                    }
                }
                else{
                    if(cost[r][c-1].F > x){
                        cost[r][c-1] = {x, 0, 0};
                        q0.pb({r, c-1});
                    }
                }
            }
        }
        q0.clear();
        swap(q0, q1);
    }
 
    cout << cost[t.F][t.S].F;
 
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:59:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int i = 0; i < q0.size(); i++){
      |                        ~~^~~~~~~~~~~
Main.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int i = 0; i < q0.size(); i++){
      |                        ~~^~~~~~~~~~~
Main.cpp:87:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int i = 0; i < q0.size(); i++){
      |                        ~~^~~~~~~~~~~

• 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