Submission #88699

#	Time	Username	Problem	Language	Result	Execution time	Memory
88699		popovicirobert	Tracks in the Snow (BOI13_tracks)	C++14	2.19 / 100	1288 ms	309456 KiB

tracks

#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 (stderr)

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

• Subtask 1: 0 / 30
• Subtask 2: 2.1875 / 70