Submission #1120296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120296		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	835 ms	78664 KiB

tracks

#include"bits/stdc++.h"
using namespace std;

using ll = long long;

const int mxN = 4003;

char g[mxN][mxN];

struct Dsu {
    int ar[mxN * mxN];
    Dsu() {
        fill(ar, ar + mxN, -1);
    }
    int Find(int u) {
        if (0 > ar[u]) {
            return u;
        } else {
            return ar[u] = Find(ar[u]);
        }
    }
    bool Unite(int u, int v) {
        u = Find(u);
        v = Find(v);
        if (u == v) {
            return false;
        }
        if (ar[u] > ar[v]) {
            swap(u, v);
        }
        ar[u] += ar[v];
        ar[v] = u;
        return true;
    }
} dsu;

main() {
    int H, W;
    cin >> H >> W;

    set<char> s;
    int visem = 0;
    for (int i = 0; i < H; i ++) {
        for (int j = 0; j < W; j ++) {
            cin >> g[i][j];
            s.insert(g[i][j]);
            if ('.' == g[i][j]) {
                visem = 1;
            }
        }
    }

    if (1 == (int)s.size() - visem) {
        cout << 1 << endl;
    } else {
        for (int i = 0; i < H; i ++) {
            for (int j = 0; j < W; j ++) {
                if (g[i][j] ^ g[0][0]) {
                    continue;
                }
                if (i + 1 < H) {
                    if (g[i + 1][j] == g[0][0]) {
                        dsu.Unite(0, (i + 1) * W + j);
                    }
                }
                if (j + 1 < W) {
                    if (g[i][j + 1] == g[0][0]) {
                        dsu.Unite(0, i * W + j + 1);
                    }
                }
            }
        }
        int ans = 2;
        for (int i = 0; i < H; i ++) {
            for (int j = 0; j < W; j ++) {
                if (g[0][0] == g[i][j]) {
                    if (dsu.Unite(0, i * W + j)) {
                        ans = 3;
                    }
                }
            }
        }
        cout << ans << endl;
    }
}

Compilation message (stderr)

tracks.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 | main() {
      | ^~~~

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