Submission #52009538

Source Code Expand

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

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef pair<int, int> Pair;
typedef tuple<int, int, int> tpl;

#define ALL(a) (a).begin(), (a).end()
#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(c) reverse((c).begin(), (c).end())
#define LB(a, x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a, x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define RREP(i, n) RFOR(i, n, 0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL << 60;
constexpr long long MOD = 998244353; // 1000000007;

template <class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

struct LowLink {
    struct Edge {
        int from, to, id = -1;
        Edge(int from, int to, int id = -1) : from(from), to(to), id(id) {}
    };

    LowLink(int N) : N(N) {
        edges.resize(N);
        ord.resize(N, N);
        low.resize(N, N);
    }

    void add_directed_edge(int u, int v, int id = -1) {
        // assume 0-indexed
        edges[u].emplace_back(u, v, id);
        while (int(back_edge.size()) <= id)
            back_edge.push_back(0);
    }

    void add_edge(int u, int v, int id = -1) {
        // assume 0-indexed
        add_directed_edge(u, v, id);
        add_directed_edge(v, u, id);
    }

    void build(int r = 0) {
        low[r] = dfs(r);
    }

    bool is_bridge(int u, int v) {
        // assume existing edge (u, v)
        if (ord[u] > ord[v])
            std::swap(u, v);
        return low[v] > ord[u];
    }

    bool is_articulation_point(int v) {
        if (ord[v] == 0) {
            return int(edges[v].size()) > 1;
        }
        for (Edge &edge : edges[v]) {
            int to = edge.to;
            if (ord[to] < ord[v])
                continue;
            if (is_back_edge(edge))
                continue;
            if (low[to] >= ord[v])
                return true;
        }
        return false;
    }

  private:
    int N, cnt = 0;
    std::vector<std::vector<Edge>> edges;
    std::vector<int> ord, low, back_edge;

    int dfs(int v = 0, int par = -1) {
        if (low[v] < N)
            return low[v];

        ord[v] = cnt++;
        low[v] = ord[v];

        for (Edge &edge : edges[v]) {
            int to = edge.to;
            if (to == par)
                continue;
            if (ord[v] > ord[to]) {
                low[v] = std::min(low[v], ord[to]);
                back_edge[edge.id] = 1;
                continue;
            }
            low[v] = std::min(low[v], dfs(to, v));
        }

        return low[v];
    }

    bool is_back_edge(Edge &edge) {
        return back_edge[edge.id] == 1;
    }
};

struct UnionFind {
    std::vector<int> par; // par[i]:iの親の番号
    std::vector<int> s;   // s[i]:iの属する木のノード数
    int n_group;          // 木の数

    UnionFind(int N) : par(N) {
        for (int i = 0; i < N; i++)
            par[i] = i;
        s.assign(N, 1);
        n_group = N;
    }

    int root(int x) { // xが属する木の根
        if (par[x] == x)
            return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x);
        int ry = root(y);
        if (rx == ry)
            return;
        par[rx] = ry;
        s[ry] += s[rx];
        s[rx] = 0;
        n_group--;
    }

    bool same(int x, int y) { // xとyが同じ木に属するかどうか
        return root(x) == root(y);
    }

    int size(int x) { // xが属する木のノード数
        return s[root(x)];
    }
};

#include <atcoder/modint>
using mint = atcoder::modint998244353;

int H, W;
vector<string> S;

void in() {
    cin >> H >> W;
    S.resize(H);
    REP(i, H)
    cin >> S[i];
}

void Main() {
    in();

    mint p(0);
    REP(i, H)
    REP(j, W)
    if (S[i][j] == '#')
        p += 1;
    if (p.val() == 0) {
        cout << 0 << en;
        return;
    }
    p = p.inv();

    UnionFind uf(H * W);
    REP(i, H)
    REP(j, W - 1)
    if (S[i][j] == '#' and S[i][j + 1] == '#')
        uf.unite(i * W + j, i * W + j + 1);
    REP(i, H - 1)
    REP(j, W)
    if (S[i][j] == '#' and S[i + 1][j] == '#')
        uf.unite(i * W + j, i * W + j + W);

    mint base(0);
    VI vis(H * W, 0);
    REP(i, H)
    REP(j, W) {
        int x = i * W + j;
        int r = uf.root(x);
        if (vis[r])
            continue;
        vis[r] = 1;
        if (S[i][j] == '#')
            base += 1;
    }

    LowLink low_link(H * W);
    int id = 0;
    REP(i, H)
    REP(j, W - 1)
    if (S[i][j] == '#' and S[i][j + 1] == '#')
        low_link.add_edge(i * W + j, i * W + j + 1, id++);
    REP(i, H - 1)
    REP(j, W)
    if (S[i][j] == '#' and S[i + 1][j] == '#')
        low_link.add_edge(i * W + j, i * W + j + W, id++);

    REP(i, H)
    REP(j, W)
    low_link.build(i * W + j);

    auto count = [&](int i, int j) {
        int cnt = 0, x = i * W + j, cnt_edge = 0;
        if (i > 0) {
            if (S[i - 1][j] == '#' and low_link.is_bridge(x, x - W))
                cnt++;
            if (S[i - 1][j] == '#')
                cnt_edge++;
        }
        if (i < H - 1) {
            if (S[i + 1][j] == '#' and low_link.is_bridge(x, x + W))
                cnt++;
            if (S[i + 1][j] == '#')
                cnt_edge++;
        }
        if (j > 0) {
            if (S[i][j - 1] == '#' and low_link.is_bridge(x, x - 1))
                cnt++;
            if (S[i][j - 1] == '#')
                cnt_edge++;
        }
        if (j < W - 1) {
            if (S[i][j + 1] == '#' and low_link.is_bridge(x, x + 1))
                cnt++;
            if (S[i][j + 1] == '#')
                cnt_edge++;
        }
        if (cnt_edge == 0)
            cnt = -1;
        else if (cnt_edge == 1)
            cnt = 0;
        else if (cnt_edge == 2) {
            cnt = cnt - (cnt == cnt_edge);
        } else if (cnt_edge == 3) {
            cnt = cnt - (cnt == cnt_edge);
        } else {
            if (cnt > 0)
                cnt = cnt - (cnt == cnt_edge);
            else
                cnt = low_link.is_articulation_point(x) * 1;
        }
        return cnt;
    };

    mint ans(0);
    REP(i, H)
    REP(j, W)
    if (S[i][j] == '#') {
        mint tmp = base + count(i, j);
        ans += p * tmp;
    }
    cout << ans.val() << en;
    return;
}

int main(void) {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    cout << fixed << setprecision(15);
    int t = 1; // cin>>t;
    while (t--)
        Main();
    return 0;
}

Submission Info

Submission Time
Task G - Christmas Color Grid 2
User Plan8
Language C++ 20 (gcc 12.2)
Score 650
Code Size 7341 Byte
Status AC
Exec Time 284 ms
Memory 162088 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 650 / 650
Status
AC × 3
AC × 34
Set Name Test Cases
Sample sample00.txt, sample01.txt, sample02.txt
All sample00.txt, sample01.txt, sample02.txt, testcase00.txt, testcase01.txt, testcase02.txt, testcase03.txt, testcase04.txt, testcase05.txt, testcase06.txt, testcase07.txt, testcase08.txt, testcase09.txt, testcase10.txt, testcase11.txt, testcase12.txt, testcase13.txt, testcase14.txt, testcase15.txt, testcase16.txt, testcase17.txt, testcase18.txt, testcase19.txt, testcase20.txt, testcase21.txt, testcase22.txt, testcase23.txt, testcase24.txt, testcase25.txt, testcase26.txt, testcase27.txt, testcase28.txt, testcase29.txt, testcase30.txt
Case Name Status Exec Time Memory
sample00.txt AC 1 ms 3396 KiB
sample01.txt AC 1 ms 3432 KiB
sample02.txt AC 1 ms 3412 KiB
testcase00.txt AC 25 ms 40268 KiB
testcase01.txt AC 29 ms 47140 KiB
testcase02.txt AC 25 ms 43632 KiB
testcase03.txt AC 29 ms 47124 KiB
testcase04.txt AC 70 ms 78400 KiB
testcase05.txt AC 79 ms 87044 KiB
testcase06.txt AC 29 ms 46044 KiB
testcase07.txt AC 29 ms 47060 KiB
testcase08.txt AC 27 ms 42124 KiB
testcase09.txt AC 31 ms 47072 KiB
testcase10.txt AC 33 ms 43628 KiB
testcase11.txt AC 37 ms 47652 KiB
testcase12.txt AC 41 ms 44464 KiB
testcase13.txt AC 45 ms 48776 KiB
testcase14.txt AC 54 ms 46868 KiB
testcase15.txt AC 57 ms 50568 KiB
testcase16.txt AC 65 ms 47308 KiB
testcase17.txt AC 71 ms 52824 KiB
testcase18.txt AC 78 ms 50096 KiB
testcase19.txt AC 86 ms 55768 KiB
testcase20.txt AC 112 ms 57084 KiB
testcase21.txt AC 122 ms 61608 KiB
testcase22.txt AC 155 ms 64108 KiB
testcase23.txt AC 166 ms 69624 KiB
testcase24.txt AC 192 ms 75088 KiB
testcase25.txt AC 227 ms 80296 KiB
testcase26.txt AC 239 ms 92072 KiB
testcase27.txt AC 262 ms 100356 KiB
testcase28.txt AC 248 ms 101880 KiB
testcase29.txt AC 284 ms 118332 KiB
testcase30.txt AC 200 ms 162088 KiB