oj.uz

Submission #88699

# Submission time Handle Problem Language Result Execution time Memory
88699 2018-12-07T15:24:20 Z popovicirobert Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 1288 ms 309456 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)) {
                        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 119 ms 80760 KB Output isn't correct
2 Incorrect 94 ms 80760 KB Output isn't correct
3 Incorrect 88 ms 80760 KB Output isn't correct
4 Incorrect 103 ms 81016 KB Output isn't correct
5 Incorrect 96 ms 81016 KB Output isn't correct
6 Incorrect 77 ms 81016 KB Output isn't correct
7 Incorrect 90 ms 81016 KB Output isn't correct
8 Incorrect 80 ms 81016 KB Output isn't correct
9 Incorrect 79 ms 81016 KB Output isn't correct
10 Incorrect 83 ms 81016 KB Output isn't correct
11 Incorrect 84 ms 81016 KB Output isn't correct
12 Incorrect 97 ms 81016 KB Output isn't correct
13 Incorrect 93 ms 81016 KB Output isn't correct
14 Incorrect 93 ms 81016 KB Output isn't correct
15 Incorrect 111 ms 82068 KB Output isn't correct
16 Incorrect 105 ms 82176 KB Output isn't correct
17 Incorrect 94 ms 82468 KB Output isn't correct
18 Incorrect 102 ms 82664 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 95648 KB Output isn't correct
2 Incorrect 171 ms 95648 KB Output isn't correct
3 Incorrect 507 ms 113776 KB Output isn't correct
4 Incorrect 199 ms 113776 KB Output isn't correct
5 Incorrect 526 ms 122444 KB Output isn't correct
6 Incorrect 1223 ms 141684 KB Output isn't correct
7 Incorrect 110 ms 141684 KB Output isn't correct
8 Incorrect 106 ms 141684 KB Output isn't correct
9 Incorrect 93 ms 141684 KB Output isn't correct
10 Incorrect 92 ms 141684 KB Output isn't correct
11 Incorrect 104 ms 141684 KB Output isn't correct
12 Incorrect 91 ms 141684 KB Output isn't correct
13 Incorrect 155 ms 141684 KB Output isn't correct
14 Incorrect 120 ms 141684 KB Output isn't correct
15 Incorrect 119 ms 141684 KB Output isn't correct
16 Incorrect 120 ms 141684 KB Output isn't correct
17 Incorrect 265 ms 142104 KB Output isn't correct
18 Incorrect 225 ms 145884 KB Output isn't correct
19 Incorrect 187 ms 149112 KB Output isn't correct
20 Incorrect 194 ms 152024 KB Output isn't correct
21 Incorrect 347 ms 166432 KB Output isn't correct
22 Incorrect 529 ms 174912 KB Output isn't correct
23 Incorrect 439 ms 180536 KB Output isn't correct
24 Incorrect 356 ms 191772 KB Output isn't correct
25 Incorrect 700 ms 210976 KB Output isn't correct
26 Correct 26 ms 210976 KB Output is correct
27 Incorrect 915 ms 238264 KB Output isn't correct
28 Incorrect 1212 ms 254032 KB Output isn't correct
29 Incorrect 1157 ms 269736 KB Output isn't correct
30 Incorrect 1049 ms 284824 KB Output isn't correct
31 Incorrect 1288 ms 290624 KB Output isn't correct
32 Incorrect 843 ms 309456 KB Output isn't correct