Submission #364120

#	Time	Username	Problem	Language	Result	Execution time	Memory
364120		rocks03	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	992 ms	122748 KiB

tracks

//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define Re(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int H, W;
vector<vector<char>> a;

int dx[] = {-1, +1, 0, 0};
int dy[] = {0, 0, -1, +1};
bool valid(int x, int y){
    return (x >= 0 && x < H && y >= 0 && y < W && a[x][y] != '.');
}

void solve(){
    cin >> H >> W;
    a = vector<vector<char>>(H, vector<char>(W));
    rep(i, 0, H){
        string s; cin >> s;
        rep(j, 0, W){
            a[i][j] = s[j];
        }
    }
    deque<pii> q;
    q.push_front({0, 0});
    vector<vector<int>> d(H, vector<int>(W, INT_MAX));
    d[0][0] = 1;
    int ans = 1;
    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop_front();
        rep(i, 0, 4){
            int x2 = x + dx[i], y2 = y + dy[i];
            if(valid(x2, y2)){
                if(a[x2][y2] != a[x][y] && d[x2][y2] > d[x][y] + 1){
                    d[x2][y2] = d[x][y] + 1;
                    q.push_back({x2, y2});
                } else if(a[x2][y2] == a[x][y] && d[x2][y2] > d[x][y]){
                    d[x2][y2] = d[x][y];
                    q.push_front({x2, y2});
                }
            }
        }
        ans = max(ans, d[x][y]);
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'void solve()':
tracks.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         auto [x, y] = q.front();
      |              ^

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