oj.uz

Submission #446111

# Submission time Handle Problem Language Result Execution time Memory
446111 2021-07-21T00:24:11 Z JovanB Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 655 ms 169724 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
int mat[4005][4005];
int n, m;
int mx = 0;
int dist[4005][4005];
 
void bfs(){
    deque <pair <int, int>> q;
    q.push_front({1, 1});
    for(int i=0; i<=n+1; i++){
        for(int j=0; j<=m+1; j++){
            dist[i][j] = 1000000000;
            if(mat[i][j] == 0) dist[i][j] = -500;
        }
    }
    dist[1][1] = 0;
    while(!q.empty()){
        pair <int, int> p = q.front();
        q.pop_front();
        int i = p.first;
        int j = p.second;
        mx = max(mx, dist[i][j]);
        if(mat[i-1][j] == mat[i][j]){
            if(dist[i][j] < dist[i-1][j]){
                dist[i-1][j] = dist[i][j];
                q.push_front({i-1, j});
            }
        }
        else{
            if(dist[i][j] + 1 < dist[i-1][j]){
                dist[i-1][j] = dist[i][j] + 1;
                q.push_back({i-1, j});
            }
        }
        if(mat[i+1][j] == mat[i][j]){
            if(dist[i][j] < dist[i+1][j]){
                dist[i+1][j] = dist[i][j];
                q.push_front({i+1, j});
            }
        }
        else{
            if(dist[i][j] + 1 < dist[i+1][j]){
                dist[i+1][j] = dist[i][j] + 1;
                q.push_back({i+1, j});
            }
        }
        if(mat[i][j-1] == mat[i][j]){
            if(dist[i][j] < dist[i][j-1]){
                dist[i][j-1] = dist[i][j];
                q.push_front({i, j-1});
            }
        }
        else{
            if(dist[i][j] + 1 < dist[i][j-1]){
                dist[i][j-1] = dist[i][j] + 1;
                q.push_back({i, j-1});
            }
        }
        if(mat[i][j] == mat[i][j+1]){
            if(dist[i][j] < dist[i][j+1]){
                dist[i][j+1] = dist[i][j];
                q.push_front({i, j+1});
            }
        }
        else{
            if(dist[i][j] + 1 < dist[i][j+1]){
                dist[i][j+1] = dist[i][j] + 1;
                q.push_back({i, j+1});
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cout.precision(10);
    cout<<fixed;
 
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        string s;
        cin >> s;
        for(int j=1; j<=m; j++){
            if(s[j-1] == 'R') mat[i][j] = 1;
            else if(s[j-1] == 'F') mat[i][j] = -1;
        }
    }
    bfs();
    cout << mx+1 << "\n";
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6476 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 8 ms 5836 KB Output is correct
5 Correct 3 ms 3276 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 3 ms 2764 KB Output is correct
11 Correct 3 ms 2252 KB Output is correct
12 Correct 6 ms 3404 KB Output is correct
13 Correct 3 ms 3268 KB Output is correct
14 Correct 4 ms 3404 KB Output is correct
15 Correct 13 ms 6344 KB Output is correct
16 Correct 16 ms 6472 KB Output is correct
17 Correct 10 ms 6220 KB Output is correct
18 Correct 8 ms 5836 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31436 KB Output is correct
2 Correct 46 ms 21376 KB Output is correct
3 Correct 233 ms 113868 KB Output is correct
4 Correct 73 ms 47556 KB Output is correct
5 Correct 158 ms 88704 KB Output is correct
6 Correct 637 ms 147980 KB Output is correct
7 Correct 16 ms 32844 KB Output is correct
8 Correct 16 ms 31476 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 16 ms 32276 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Correct 49 ms 21248 KB Output is correct
14 Correct 28 ms 14028 KB Output is correct
15 Correct 28 ms 17096 KB Output is correct
16 Correct 22 ms 8268 KB Output is correct
17 Correct 115 ms 44992 KB Output is correct
18 Correct 102 ms 51652 KB Output is correct
19 Correct 71 ms 47556 KB Output is correct
20 Correct 60 ms 39324 KB Output is correct
21 Correct 145 ms 89000 KB Output is correct
22 Correct 161 ms 88772 KB Output is correct
23 Correct 208 ms 73276 KB Output is correct
24 Correct 149 ms 85700 KB Output is correct
25 Correct 474 ms 134752 KB Output is correct
26 Correct 349 ms 169724 KB Output is correct
27 Correct 459 ms 152516 KB Output is correct
28 Correct 652 ms 148044 KB Output is correct
29 Correct 626 ms 148428 KB Output is correct
30 Correct 561 ms 146904 KB Output is correct
31 Correct 655 ms 111104 KB Output is correct
32 Correct 414 ms 150248 KB Output is correct