oj.uz

Submission #437672

# Submission time Handle Problem Language Result Execution time Memory
437672 2021-06-26T19:57:07 Z MohammadAghil Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 637 ms 165472 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[i] == 'R') a[i][j] = 1;
            else if(s[i] == '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;
            int 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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4300 KB Output isn't correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Incorrect 1 ms 460 KB Output isn't correct
4 Incorrect 8 ms 3416 KB Output isn't correct
5 Incorrect 2 ms 1240 KB Output isn't correct
6 Incorrect 1 ms 332 KB Output isn't correct
7 Incorrect 1 ms 460 KB Output isn't correct
8 Incorrect 1 ms 588 KB Output isn't correct
9 Incorrect 1 ms 460 KB Output isn't correct
10 Incorrect 2 ms 1228 KB Output isn't correct
11 Incorrect 3 ms 1484 KB Output isn't correct
12 Incorrect 2 ms 2148 KB Output isn't correct
13 Incorrect 2 ms 1224 KB Output isn't correct
14 Incorrect 2 ms 1228 KB Output isn't correct
15 Incorrect 4 ms 3916 KB Output isn't correct
16 Incorrect 5 ms 4300 KB Output isn't correct
17 Incorrect 4 ms 3020 KB Output isn't correct
18 Incorrect 5 ms 3404 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 716 KB Output isn't correct
2 Incorrect 14 ms 13268 KB Output isn't correct
3 Incorrect 104 ms 96072 KB Output isn't correct
4 Incorrect 28 ms 22476 KB Output isn't correct
5 Incorrect 67 ms 68052 KB Output isn't correct
6 Incorrect 605 ms 142712 KB Output isn't correct
7 Incorrect 4 ms 844 KB Output isn't correct
8 Incorrect 4 ms 716 KB Output isn't correct
9 Incorrect 1 ms 588 KB Output isn't correct
10 Incorrect 1 ms 460 KB Output isn't correct
11 Runtime error 6 ms 464 KB Execution killed with signal 11
12 Incorrect 1 ms 716 KB Output isn't correct
13 Incorrect 14 ms 13260 KB Output isn't correct
14 Incorrect 11 ms 8048 KB Output isn't correct
15 Incorrect 10 ms 7500 KB Output isn't correct
16 Incorrect 7 ms 4940 KB Output isn't correct
17 Incorrect 31 ms 30380 KB Output isn't correct
18 Incorrect 29 ms 26516 KB Output isn't correct
19 Incorrect 26 ms 22328 KB Output isn't correct
20 Incorrect 25 ms 23040 KB Output isn't correct
21 Incorrect 62 ms 58632 KB Output isn't correct
22 Incorrect 68 ms 68128 KB Output isn't correct
23 Incorrect 67 ms 57548 KB Output isn't correct
24 Incorrect 74 ms 60740 KB Output isn't correct
25 Incorrect 104 ms 101220 KB Output isn't correct
26 Correct 466 ms 165472 KB Output is correct
27 Incorrect 544 ms 151464 KB Output isn't correct
28 Incorrect 569 ms 142628 KB Output isn't correct
29 Incorrect 582 ms 142860 KB Output isn't correct
30 Incorrect 637 ms 160508 KB Output isn't correct
31 Incorrect 82 ms 100548 KB Output isn't correct
32 Incorrect 159 ms 129728 KB Output isn't correct