oj.uz

Submission #88700

# Submission time Handle Problem Language Result Execution time Memory
88700 2018-12-07T15:26:59 Z popovicirobert Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 1173 ms 96796 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 sef[MAXN * MAXN + 1];

int myfind(int x) {
    if(sef[x] == 0)
        return x;
    return sef[x] = myfind(sef[x]);
}

inline void myunion(int x, int y) {
    x = myfind(x), y = myfind(y);
    if(x != y) {
        sef[x] = y;
    }
}

bool vis[MAXN * 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;
}

inline int get(int l, int c) {
    return (l - 1) * m + c;
}

inline int solve(char ch) {
    int i, j;
    memset(sef, 0, sizeof(sef));
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            if(mat[i][j] == ch) {
                for(int p = 0; p < 4; p++) {
                    int l = i + dl[p], c = j + dc[p];
                    if(in(l, c) && mat[l][c] == ch) {
                        myunion(get(l, c), get(i, j));
                    }
                }
            }
        }
    }
    memset(vis, 0, sizeof(vis));
    int ans = 1;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            if(mat[i][j] == ch) {
                if(!vis[myfind(get(i, j))]) {
                    vis[myfind(get(i, j))] = 1;
                    ans++;
                }
            }
        }
    }
    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('R');
    ans = min(ans, solve('F'));
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message

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

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 80964 KB Output isn't correct
2 Incorrect 90 ms 80964 KB Output isn't correct
3 Incorrect 90 ms 80964 KB Output isn't correct
4 Incorrect 101 ms 81256 KB Output isn't correct
5 Incorrect 93 ms 81256 KB Output isn't correct
6 Incorrect 78 ms 81256 KB Output isn't correct
7 Incorrect 78 ms 81256 KB Output isn't correct
8 Incorrect 78 ms 81256 KB Output isn't correct
9 Incorrect 77 ms 81256 KB Output isn't correct
10 Incorrect 81 ms 81256 KB Output isn't correct
11 Incorrect 79 ms 81256 KB Output isn't correct
12 Incorrect 85 ms 81256 KB Output isn't correct
13 Incorrect 82 ms 81256 KB Output isn't correct
14 Incorrect 79 ms 81256 KB Output isn't correct
15 Incorrect 101 ms 81972 KB Output isn't correct
16 Incorrect 101 ms 82108 KB Output isn't correct
17 Incorrect 89 ms 82244 KB Output isn't correct
18 Incorrect 92 ms 82452 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 95572 KB Output isn't correct
2 Incorrect 133 ms 95572 KB Output isn't correct
3 Incorrect 413 ms 96576 KB Output isn't correct
4 Incorrect 166 ms 96576 KB Output isn't correct
5 Incorrect 191 ms 96576 KB Output isn't correct
6 Incorrect 1173 ms 96576 KB Output isn't correct
7 Incorrect 104 ms 96576 KB Output isn't correct
8 Incorrect 104 ms 96576 KB Output isn't correct
9 Incorrect 90 ms 96576 KB Output isn't correct
10 Incorrect 92 ms 96576 KB Output isn't correct
11 Incorrect 91 ms 96576 KB Output isn't correct
12 Incorrect 80 ms 96576 KB Output isn't correct
13 Incorrect 146 ms 96576 KB Output isn't correct
14 Incorrect 116 ms 96576 KB Output isn't correct
15 Incorrect 106 ms 96576 KB Output isn't correct
16 Incorrect 121 ms 96576 KB Output isn't correct
17 Incorrect 218 ms 96576 KB Output isn't correct
18 Incorrect 185 ms 96576 KB Output isn't correct
19 Incorrect 154 ms 96576 KB Output isn't correct
20 Incorrect 156 ms 96576 KB Output isn't correct
21 Incorrect 278 ms 96576 KB Output isn't correct
22 Incorrect 193 ms 96576 KB Output isn't correct
23 Incorrect 347 ms 96576 KB Output isn't correct
24 Incorrect 294 ms 96576 KB Output isn't correct
25 Incorrect 521 ms 96592 KB Output isn't correct
26 Correct 36 ms 96592 KB Output is correct
27 Incorrect 923 ms 96796 KB Output isn't correct
28 Incorrect 1163 ms 96796 KB Output isn't correct
29 Incorrect 1151 ms 96796 KB Output isn't correct
30 Incorrect 1062 ms 96796 KB Output isn't correct
31 Incorrect 1008 ms 96796 KB Output isn't correct
32 Incorrect 918 ms 96796 KB Output isn't correct