oj.uz

Submission #796592

# Submission time Handle Problem Language Result Execution time Memory
796592 2023-07-28T14:33:09 Z phongcd Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 621 ms 172008 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6356 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 8 ms 5968 KB Output is correct
5 Correct 4 ms 3284 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 3 ms 2260 KB Output is correct
12 Correct 5 ms 3412 KB Output is correct
13 Correct 3 ms 3284 KB Output is correct
14 Correct 3 ms 3284 KB Output is correct
15 Correct 11 ms 6064 KB Output is correct
16 Correct 12 ms 6448 KB Output is correct
17 Correct 10 ms 6100 KB Output is correct
18 Correct 7 ms 5844 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31328 KB Output is correct
2 Correct 46 ms 18344 KB Output is correct
3 Correct 319 ms 99300 KB Output is correct
4 Correct 94 ms 46652 KB Output is correct
5 Correct 182 ms 74000 KB Output is correct
6 Correct 616 ms 154100 KB Output is correct
7 Correct 15 ms 32720 KB Output is correct
8 Correct 14 ms 31328 KB Output is correct
9 Correct 2 ms 852 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 14 ms 32088 KB Output is correct
12 Correct 2 ms 1748 KB Output is correct
13 Correct 56 ms 18432 KB Output is correct
14 Correct 28 ms 12456 KB Output is correct
15 Correct 28 ms 17084 KB Output is correct
16 Correct 21 ms 7248 KB Output is correct
17 Correct 115 ms 37456 KB Output is correct
18 Correct 107 ms 51504 KB Output is correct
19 Correct 88 ms 46668 KB Output is correct
20 Correct 76 ms 33548 KB Output is correct
21 Correct 176 ms 71528 KB Output is correct
22 Correct 187 ms 74068 KB Output is correct
23 Correct 225 ms 59532 KB Output is correct
24 Correct 180 ms 65920 KB Output is correct
25 Correct 544 ms 141232 KB Output is correct
26 Correct 510 ms 172008 KB Output is correct
27 Correct 519 ms 160988 KB Output is correct
28 Correct 621 ms 154084 KB Output is correct
29 Correct 593 ms 152932 KB Output is correct
30 Correct 604 ms 151820 KB Output is correct
31 Correct 470 ms 111124 KB Output is correct
32 Correct 523 ms 149440 KB Output is correct