Submission #816464

#	Time	Username	Problem	Language	Result	Execution time	Memory
816464		QwertyPi	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	734 ms	152908 KiB

tracks

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;

const int MAXN = 4e3 + 11;
char c[MAXN][MAXN];
int d[MAXN][MAXN];
bool vis[MAXN][MAXN];

int h, w;
bool in(int i, int j){
    return 1 <= i && i <= h && 1 <= j && j <= w && c[i][j] != '.';
}
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

struct point{
    int x, y;
    bool operator< (const point& o) const {
        return x < o.x || x == o.x && y < o.y;
    }
};

int32_t main(){
    cin.tie(0); cout.tie(0)->sync_with_stdio(false);
    cin >> h >> w;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> c[i][j];
        }
    }

    memset(d, 0x3f, sizeof(d));
    d[1][1] = 0;
    deque<point> dq; dq.push_back({1, 1});
    while(!dq.empty()){
        auto [x, y] = dq.front(); dq.pop_front();
        if(vis[x][y]) continue; vis[x][y] = true;
        for(int dir = 0; dir < 4; dir++){
            int nx = x + dx[dir], ny = y + dy[dir];
            if(!in(nx, ny)) continue;
            if(d[nx][ny] > d[x][y] + (c[x][y] != c[nx][ny])){
                d[nx][ny] = d[x][y] + (c[x][y] != c[nx][ny]);
                if(c[x][y] == c[nx][ny]){
                    dq.push_front({nx, ny});
                }else{
                    dq.push_back({nx, ny});
                }
            }
        }
    }

    int ans = 0;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            if(c[i][j] != '.') ans = max(ans, d[i][j]);
        }
    }
    cout << ans + 1 << endl;
}

Compilation message (stderr)

tracks.cpp: In member function 'bool point::operator<(const point&) const':
tracks.cpp:21:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   21 |         return x < o.x || x == o.x && y < o.y;
      |                           ~~~~~~~~~^~~~~~~~~~
tracks.cpp: In function 'int32_t main()':
tracks.cpp:38:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         auto [x, y] = dq.front(); dq.pop_front();
      |              ^
tracks.cpp:39:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   39 |         if(vis[x][y]) continue; vis[x][y] = true;
      |         ^~
tracks.cpp:39:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   39 |         if(vis[x][y]) continue; vis[x][y] = true;
      |                                 ^~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70