oj.uz

Submission #757356

# Submission time Handle Problem Language Result Execution time Memory
757356 2023-06-13T05:58:11 Z dxz05 Tracks in the Snow (BOI13_tracks) C++17
43.125 / 100
 2000 ms 21988 KB 
#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];
void solve(){
    int n, m;
    cin >> n >> m;

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

    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;

    while (true){
        ans++;

        queue<pair<int, int>> q;
        q.emplace(0, 0);

        vector<vector<bool>> used(n, vector<bool>(m, false));
        used[0][0] = true;
        a[0][0] = '?';

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

            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);
                        used[i][j] = true;
                        a[i][j] = '?';
                    }
                }

            }

        }

        animal ^= 'F' ^ 'R';

        bool TUGADI = true;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (a[i][j] == 'F' || a[i][j] == 'R') TUGADI = false;
            }
        }

        if (TUGADI) break;
    }

    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

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 2524 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 22 ms 2388 KB Output is correct
5 Correct 72 ms 1492 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 4 ms 728 KB Output is correct
10 Correct 81 ms 1284 KB Output is correct
11 Correct 5 ms 1108 KB Output is correct
12 Correct 59 ms 1496 KB Output is correct
13 Correct 76 ms 1552 KB Output is correct
14 Correct 71 ms 1544 KB Output is correct
15 Correct 468 ms 2576 KB Output is correct
16 Correct 177 ms 2648 KB Output is correct
17 Correct 470 ms 2472 KB Output is correct
18 Correct 19 ms 2392 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 15572 KB Time limit exceeded
2 Execution timed out 2045 ms 7116 KB Time limit exceeded
3 Execution timed out 2027 ms 20456 KB Time limit exceeded
4 Execution timed out 2059 ms 11660 KB Time limit exceeded
5 Execution timed out 2017 ms 16360 KB Time limit exceeded
6 Execution timed out 2059 ms 20468 KB Time limit exceeded
7 Execution timed out 2051 ms 16308 KB Time limit exceeded
8 Execution timed out 2061 ms 15580 KB Time limit exceeded
9 Correct 155 ms 340 KB Output is correct
10 Correct 365 ms 380 KB Output is correct
11 Correct 1126 ms 16004 KB Output is correct
12 Correct 1668 ms 936 KB Output is correct
13 Execution timed out 2037 ms 7116 KB Time limit exceeded
14 Execution timed out 2061 ms 4972 KB Time limit exceeded
15 Execution timed out 2041 ms 5324 KB Time limit exceeded
16 Execution timed out 2063 ms 2516 KB Time limit exceeded
17 Execution timed out 2058 ms 12180 KB Time limit exceeded
18 Execution timed out 2055 ms 12188 KB Time limit exceeded
19 Execution timed out 2061 ms 11684 KB Time limit exceeded
20 Execution timed out 2043 ms 10988 KB Time limit exceeded
21 Execution timed out 2025 ms 16716 KB Time limit exceeded
22 Execution timed out 2062 ms 16420 KB Time limit exceeded
23 Execution timed out 2029 ms 14280 KB Time limit exceeded
24 Execution timed out 2078 ms 16884 KB Time limit exceeded
25 Execution timed out 2040 ms 20556 KB Time limit exceeded
26 Correct 455 ms 19008 KB Output is correct
27 Correct 1930 ms 21848 KB Output is correct
28 Execution timed out 2032 ms 21948 KB Time limit exceeded
29 Execution timed out 2044 ms 21876 KB Time limit exceeded
30 Execution timed out 2074 ms 21412 KB Time limit exceeded
31 Execution timed out 2035 ms 17388 KB Time limit exceeded
32 Execution timed out 2059 ms 21988 KB Time limit exceeded