oj.uz

Submission #757467

# Submission time Handle Problem Language Result Execution time Memory
757467 2023-06-13T08:21:29 Z The_Samurai Tracks in the Snow (BOI13_tracks) C++17
49.6875 / 100
 2000 ms 165656 KB 
#include "bits/stdc++.h"

using namespace std;

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    clock_t startTime = clock();

    int n, m;
    cin >> n >> m;
    vector<vector<char>> a(n, vector<char>(m, '.'));
    auto nw = a;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    if (max(n, m) == 1) {
        cout << 1;
        return 0;
    }
    vector<pair<int, int>> can = {{0, 0}};
    vector<vector<bool>> vis(n, vector<bool>(m));
    char x = a[0][0];
    nw[0][0] = x;
    vis[0][0] = true;
    int ans = 0;
    while (nw != a) {
        ans++;
        for (int p = 0; p < can.size(); p++) {
            auto [i, j] = can[p];
            for (int k = 0; k < 4; k++) {
                int ii = i + dx[k];
                int jj = j + dy[k];
                if (min(ii, jj) < 0 or ii == n or jj == m) continue;
                if (vis[ii][jj]) continue;
                if (a[ii][jj] == x) {
                    can.emplace_back(ii, jj);
                    vis[ii][jj] = true;
                    nw[ii][jj] = x;
                }
            }
        }
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++) {
//                cout << nw[i][j];
//            }
//            cout << endl;
//        }
//        cout << endl;
        x = (x == 'R' ? 'F' : 'R');
    }
    cout << ans;



#ifdef sunnitov
    cerr << "\nTime: " << (int)((double)(clock() - startTime) / CLOCKS_PER_SEC * 1000);
#endif
}

/*
 5 6
 FFFFFF
 RRRRRF
 F...RF
 F...RF
 F..RRF
 FFFRRF
*/

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:34:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (int p = 0; p < can.size(); p++) {
      |                         ~~^~~~~~~~~~~~
tracks.cpp:11:13: warning: unused variable 'startTime' [-Wunused-variable]
   11 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 3016 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 19 ms 2832 KB Output is correct
5 Correct 53 ms 920 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 70 ms 856 KB Output is correct
11 Correct 4 ms 984 KB Output is correct
12 Correct 39 ms 1612 KB Output is correct
13 Correct 50 ms 852 KB Output is correct
14 Correct 51 ms 900 KB Output is correct
15 Correct 355 ms 3056 KB Output is correct
16 Correct 131 ms 2952 KB Output is correct
17 Correct 339 ms 1996 KB Output is correct
18 Correct 17 ms 2768 KB Output is correct

Subtask #2
19.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 754 ms 1372 KB Output is correct
2 Execution timed out 2068 ms 12076 KB Time limit exceeded
3 Execution timed out 2084 ms 34804 KB Time limit exceeded
4 Execution timed out 2078 ms 12616 KB Time limit exceeded
5 Execution timed out 2073 ms 19796 KB Time limit exceeded
6 Execution timed out 2069 ms 165652 KB Time limit exceeded
7 Correct 636 ms 1272 KB Output is correct
8 Correct 745 ms 1228 KB Output is correct
9 Correct 137 ms 784 KB Output is correct
10 Correct 229 ms 700 KB Output is correct
11 Correct 218 ms 1140 KB Output is correct
12 Correct 1018 ms 684 KB Output is correct
13 Execution timed out 2063 ms 12176 KB Time limit exceeded
14 Execution timed out 2070 ms 6608 KB Time limit exceeded
15 Execution timed out 2076 ms 3100 KB Time limit exceeded
16 Execution timed out 2075 ms 5928 KB Time limit exceeded
17 Execution timed out 2070 ms 17352 KB Time limit exceeded
18 Execution timed out 2072 ms 9496 KB Time limit exceeded
19 Execution timed out 2031 ms 12712 KB Time limit exceeded
20 Execution timed out 2071 ms 8328 KB Time limit exceeded
21 Execution timed out 2059 ms 20792 KB Time limit exceeded
22 Execution timed out 2081 ms 19892 KB Time limit exceeded
23 Execution timed out 2053 ms 25100 KB Time limit exceeded
24 Execution timed out 2061 ms 20196 KB Time limit exceeded
25 Execution timed out 2070 ms 34780 KB Time limit exceeded
26 Correct 610 ms 157668 KB Output is correct
27 Correct 1749 ms 165572 KB Output is correct
28 Execution timed out 2068 ms 165544 KB Time limit exceeded
29 Execution timed out 2082 ms 165656 KB Time limit exceeded
30 Execution timed out 2082 ms 164912 KB Time limit exceeded
31 Execution timed out 2085 ms 55072 KB Time limit exceeded
32 Execution timed out 2068 ms 165516 KB Time limit exceeded