Submission #796592

#	Time	Username	Problem	Language	Result	Execution time	Memory
796592		phongcd	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	621 ms	172008 KiB

tracks

#include <bits/stdc++.h>
#define ll long long
#define ld long  double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 4e3 + 2;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ll base = 311;
const int BLOCK_SIZE = 2000;
 
int n, m;
int a[N][N], vis[N][N];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

void maximize(int &a, int b) {
    if (a < b) a = b;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
    // #endif
 
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++) {
            char x; cin >> x;
            if (x == 'R') a[i][j] = 1;
            else if (x == 'F') a[i][j] = 2;
        }

    deque <ii> h;
    h.push_back({1, 1});
    vis[1][1] = 1;

    int ans = 0;
    while (!h.empty()) {
        auto [x, y] = h.front(); h.pop_front();
        maximize(ans, vis[x][y]);
        for (int j = 0; j < 4; j ++) {
            int u = x + dx[j];
            int v = y + dy[j];
            if (a[u][v] && !vis[u][v]) {
                if (a[u][v] != a[x][y]) {
                    vis[u][v] = vis[x][y] + 1;
                    h.push_back({u, v});
                }
                else {
                    vis[u][v] = vis[x][y];
                    h.push_front({u, v});
                } 
            }
        }
    }
    cout << ans;
}
/*
     /\_/\ zzZ
    (= -_-)
    / >u  >u
*/

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:47:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |         auto [x, y] = h.front(); h.pop_front();
      |              ^

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