Submission #757361

#	Time	Username	Problem	Language	Result	Execution time	Memory
757361		dxz05	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1079 ms	42024 KiB

tracks

#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 4004;

char a[N][N];
bool used[N][N];

void solve(){
    int n, m;
    cin >> n >> m;

    int animals_cnt = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> a[i][j];
            animals_cnt += a[i][j] == 'F' || a[i][j] == 'R';
        }
    }

    char animal = a[0][0];

    if (animal == '.'){
        cout << 0 << endl;
        return;
    }

    vector<int> dx = {0, 1, 0, -1};
    vector<int> dy = {1, 0, -1, 0};

    int ans = 0;

    queue<pair<int, int>> q;
    q.emplace(0, 0);
    used[0][0] = true;

    queue<pair<int, int>> _q;

    while (animals_cnt){
        ans++;

        while (!q.empty()){
            auto [x, y] = q.front();
            q.pop();

            if (a[x][y] == animal) animals_cnt--;
            a[x][y] = '?';

            for (int it = 0; it < 4; it++){
                int i = x + dx[it];
                int j = y + dy[it];

                if (i >= 0 && i < n && j >= 0 && j < m && !used[i][j]){
                    if (a[i][j] == '?' || a[i][j] == animal){
                        q.emplace(i, j);
                    } else if (a[i][j] != '.'){
                        _q.emplace(i, j);
                    }
                    used[i][j] = true;
                }

            }

        }

        q.swap(_q);

        animal ^= 'F' ^ 'R';
    }

    cout << ans << endl;

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
//    cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:91:13: warning: unused variable 'startTime' [-Wunused-variable]
   91 |     clock_t startTime = clock();
      |             ^~~~~~~~~

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