oj.uz

Submission #88705

# Submission time Handle Problem Language Result Execution time Memory
88705 2018-12-07T15:57:51 Z popovicirobert Tracks in the Snow (BOI13_tracks) C++14
19.7917 / 100
 1181 ms 97876 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int INF = 2e9;
const int MAXN = 4000;

char mat[MAXN + 1][MAXN + 1];

int dist[MAXN + 1][MAXN + 1];
char dl[] = {-1, 0, 1, 0}, dc[] = {0, -1, 0, 1};
int n, m;

inline bool in(int l, int c) {
    return 1 <= l && l <= n && 1 <= c && c <= m;
}

deque < pair <short, short> > deq;

inline int solve() {
    int i, j;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            dist[i][j] = INF;
        }
    }
    deq.push_back({1, 1});
    dist[1][1] = 1;
    while(deq.size()) {
        int l = deq.front().first;
        int c = deq.front().second;
        deq.pop_front();
        for(i = 0; i < 4; i++) {
            int lin = l + dl[i];
            int col = c + dc[i];
            if(in(lin, col)) {
                int cur = dist[l][c] + (mat[l][c] != mat[lin][col]);
                if(dist[lin][col] > cur) {
                    dist[lin][col] = cur;
                    if(mat[lin][col] == mat[l][c]) {
                        deq.push_front({lin, col});
                    }
                    else {
                        deq.push_back({lin, col});
                    }
                }
            }
        }
    }
    int ans = 0;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            if(mat[i][j] != '.') {
                ans = max(ans, dist[i][j]);
            }
        }
    }
    return ans;
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, j;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    int cntF = 0, cntR = 0;
    for(i = 1; i <= n; i++) {
        cin >> mat[i] + 1;
        for(j = 1; j <= m; j++) {
            if(mat[i][j] == 'R') {
                cntR++;
            }
            if(mat[i][j] == 'F') {
                cntF++;
            }
        }
    }
    if(cntF + cntR == 0) {
        cout << 0;
        return 0;
    }
    if(cntF == 0 || cntR == 0) {
        cout << 1;
        return 0;
    }
    int ans = solve();
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:75:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin >> mat[i] + 1;
                ~~~~~~~^~~

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 5240 KB Output isn't correct
2 Incorrect 2 ms 5240 KB Output isn't correct
3 Incorrect 2 ms 5240 KB Output isn't correct
4 Correct 11 ms 5240 KB Output is correct
5 Incorrect 7 ms 5240 KB Output isn't correct
6 Incorrect 2 ms 5240 KB Output isn't correct
7 Incorrect 2 ms 5240 KB Output isn't correct
8 Correct 2 ms 5240 KB Output is correct
9 Incorrect 3 ms 5240 KB Output isn't correct
10 Incorrect 6 ms 5240 KB Output isn't correct
11 Correct 5 ms 5240 KB Output is correct
12 Incorrect 8 ms 5240 KB Output isn't correct
13 Incorrect 7 ms 5240 KB Output isn't correct
14 Incorrect 7 ms 5240 KB Output isn't correct
15 Incorrect 17 ms 5728 KB Output isn't correct
16 Incorrect 17 ms 5728 KB Output isn't correct
17 Incorrect 16 ms 5728 KB Output isn't correct
18 Correct 10 ms 5728 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 31072 KB Output isn't correct
2 Incorrect 73 ms 31072 KB Output isn't correct
3 Incorrect 602 ms 95732 KB Output isn't correct
4 Incorrect 190 ms 95732 KB Output isn't correct
5 Incorrect 317 ms 95732 KB Output isn't correct
6 Correct 802 ms 95732 KB Output is correct
7 Incorrect 29 ms 95732 KB Output isn't correct
8 Incorrect 27 ms 95732 KB Output isn't correct
9 Incorrect 4 ms 95732 KB Output isn't correct
10 Incorrect 3 ms 95732 KB Output isn't correct
11 Incorrect 28 ms 95732 KB Output isn't correct
12 Incorrect 4 ms 95732 KB Output isn't correct
13 Incorrect 80 ms 95732 KB Output isn't correct
14 Incorrect 45 ms 95732 KB Output isn't correct
15 Incorrect 55 ms 95732 KB Output isn't correct
16 Incorrect 32 ms 95732 KB Output isn't correct
17 Incorrect 181 ms 95732 KB Output isn't correct
18 Incorrect 261 ms 95732 KB Output isn't correct
19 Incorrect 163 ms 95732 KB Output isn't correct
20 Incorrect 140 ms 95732 KB Output isn't correct
21 Incorrect 378 ms 95732 KB Output isn't correct
22 Incorrect 311 ms 95732 KB Output isn't correct
23 Incorrect 331 ms 95732 KB Output isn't correct
24 Incorrect 338 ms 95732 KB Output isn't correct
25 Incorrect 1181 ms 97876 KB Output isn't correct
26 Correct 35 ms 97876 KB Output is correct
27 Correct 654 ms 97876 KB Output is correct
28 Correct 848 ms 97876 KB Output is correct
29 Correct 787 ms 97876 KB Output is correct
30 Correct 689 ms 97876 KB Output is correct
31 Incorrect 594 ms 97876 KB Output isn't correct
32 Incorrect 549 ms 97876 KB Output isn't correct