oj.uz

Submission #88704

# Submission time Handle Problem Language Result Execution time Memory
88704 2018-12-07T15:54:24 Z popovicirobert Tracks in the Snow (BOI13_tracks) C++14
19.7917 / 100
 1051 ms 97932 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 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;
    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)) {
                if(dist[lin][col] > 0) {
                    continue;
                }
                dist[lin][col] = dist[l][c] + (mat[l][c] != mat[lin][col]);
                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:69: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 18 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 3 ms 5240 KB Output is correct
9 Incorrect 3 ms 5240 KB Output isn't correct
10 Incorrect 7 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 13 ms 5756 KB Output isn't correct
16 Incorrect 18 ms 5756 KB Output isn't correct
17 Incorrect 16 ms 5756 KB Output isn't correct
18 Correct 11 ms 5756 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 31100 KB Output isn't correct
2 Incorrect 76 ms 31100 KB Output isn't correct
3 Incorrect 573 ms 95624 KB Output isn't correct
4 Incorrect 156 ms 95624 KB Output isn't correct
5 Incorrect 323 ms 95624 KB Output isn't correct
6 Correct 698 ms 95624 KB Output is correct
7 Incorrect 33 ms 95624 KB Output isn't correct
8 Incorrect 31 ms 95624 KB Output isn't correct
9 Incorrect 4 ms 95624 KB Output isn't correct
10 Incorrect 3 ms 95624 KB Output isn't correct
11 Incorrect 33 ms 95624 KB Output isn't correct
12 Incorrect 4 ms 95624 KB Output isn't correct
13 Incorrect 68 ms 95624 KB Output isn't correct
14 Incorrect 40 ms 95624 KB Output isn't correct
15 Incorrect 55 ms 95624 KB Output isn't correct
16 Incorrect 28 ms 95624 KB Output isn't correct
17 Incorrect 158 ms 95624 KB Output isn't correct
18 Incorrect 242 ms 95624 KB Output isn't correct
19 Incorrect 168 ms 95624 KB Output isn't correct
20 Incorrect 133 ms 95624 KB Output isn't correct
21 Incorrect 321 ms 95624 KB Output isn't correct
22 Incorrect 319 ms 95624 KB Output isn't correct
23 Incorrect 288 ms 95624 KB Output isn't correct
24 Incorrect 319 ms 95624 KB Output isn't correct
25 Incorrect 1051 ms 97932 KB Output isn't correct
26 Correct 31 ms 97932 KB Output is correct
27 Correct 507 ms 97932 KB Output is correct
28 Correct 681 ms 97932 KB Output is correct
29 Correct 669 ms 97932 KB Output is correct
30 Correct 643 ms 97932 KB Output is correct
31 Incorrect 578 ms 97932 KB Output isn't correct
32 Incorrect 502 ms 97932 KB Output isn't correct