oj.uz

Submission #437673

# Submission time Handle Problem Language Result Execution time Memory
437673 2021-06-26T20:03:17 Z MohammadAghil Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 851 ms 155296 KB 
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
#define rep(i,l,r) for(int i = (l); i < r; i++)
#define per(i,r,l) for(int i = (r); i >= l; i--)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define ss second 

const ll mod = 1e9 + 7, maxn = 4e3 + 5, inf = 1e9 + 5;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int a[maxn][maxn];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    rep(i,0,n){
        string s; cin >> s;
        rep(j,0,m){
            if(s[j] == 'R') a[i][j] = 1;
            else if(s[j] == 'F') a[i][j] = 2;
        }
    }
    vector<vector<int>> dist(n, vector<int>(m, inf));
    dist[0][0] = 1;
    deque<pair<int, int>> q; q.pb({0, 0});
    while(sz(q)){
        int i = q.front().ff, j = q.front().ss; q.pop_front();
        rep(d,0,4){
            int r = dx[d] + i, c = dy[d] + j;
            if(r < 0 || r >= n || c < 0 || c >= m || !a[r][c]) continue;
            bool w = (a[i][j] != a[r][c]);
            if(dist[r][c] > dist[i][j] + w){
                dist[r][c] = dist[i][j] + w;
                if(w){
                    q.push_back({r, c});
                }else{
                    q.push_front({r, c});
                }
            }
        }
    }
    int ans = 0;
    rep(i,0,n){
        rep(j,0,m){
            if(a[i][j]) ans = max(ans, dist[i][j]);
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4172 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 8 ms 3764 KB Output is correct
5 Correct 3 ms 2084 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 3 ms 1612 KB Output is correct
11 Correct 3 ms 1484 KB Output is correct
12 Correct 6 ms 2124 KB Output is correct
13 Correct 3 ms 1996 KB Output is correct
14 Correct 3 ms 1996 KB Output is correct
15 Correct 15 ms 4044 KB Output is correct
16 Correct 15 ms 4268 KB Output is correct
17 Correct 11 ms 4044 KB Output is correct
18 Correct 9 ms 3760 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16076 KB Output is correct
2 Correct 56 ms 14840 KB Output is correct
3 Correct 256 ms 104840 KB Output is correct
4 Correct 96 ms 36420 KB Output is correct
5 Correct 194 ms 68192 KB Output is correct
6 Correct 851 ms 140512 KB Output is correct
7 Correct 10 ms 16844 KB Output is correct
8 Correct 9 ms 16076 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 11 ms 16480 KB Output is correct
12 Correct 2 ms 1100 KB Output is correct
13 Correct 51 ms 14764 KB Output is correct
14 Correct 29 ms 9420 KB Output is correct
15 Correct 28 ms 12108 KB Output is correct
16 Correct 25 ms 6068 KB Output is correct
17 Correct 135 ms 32892 KB Output is correct
18 Correct 116 ms 39628 KB Output is correct
19 Correct 91 ms 36480 KB Output is correct
20 Correct 64 ms 28956 KB Output is correct
21 Correct 159 ms 67976 KB Output is correct
22 Correct 224 ms 68212 KB Output is correct
23 Correct 263 ms 56900 KB Output is correct
24 Correct 165 ms 64472 KB Output is correct
25 Correct 657 ms 125820 KB Output is correct
26 Correct 452 ms 153440 KB Output is correct
27 Correct 631 ms 155296 KB Output is correct
28 Correct 830 ms 140496 KB Output is correct
29 Correct 829 ms 136376 KB Output is correct
30 Correct 721 ms 143216 KB Output is correct
31 Correct 684 ms 91204 KB Output is correct
32 Correct 593 ms 145412 KB Output is correct