WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM691 Div1 Easy " Sunnygraphs"

解法

下の記事を参考にしました。m(_ _)m
kmjp.hatenablog.jp

有効グラフで考えたときに、頂点を以下のように色分けする。

A・・・0,1どちらからも到達できる頂点
B・・・0からのみ到達できる頂点
C・・・1からのみ到達できる頂点
D・・・0,1どちらからも到達できない頂点

そしたら、0と1を繋げる方法を以下のパターンで考える

パターン1・・・B及びCの辺を、どちらも頂点Nに繋げないとする。
すると、A,Dの辺については自由に動かせる。
(初期グラフで既に0と1が繋がっている事が条件だが)

パターン2・・・Bの辺を頂点Nに繋げるとする。
すると、AまたはCの辺を頂点Nに繋げる必要がでてくる。
Dの辺については自由に動かせる。

パターン3・・・Cの辺を頂点Nに繋げるとする。
すると、AまたはBの辺を頂点Nに繋げる必要がでてくる。
Dの辺については自由に動かせる。

パターン4・・・BおよびCの辺を頂点Nに繋げるとする。
すると、A,Dの辺については自由に動かせる。

パターン2でBとCの辺を頂点Nに繋げている場合があるが、これはパターン4に含まれるので排除する。
パターン3でも同様にその部分を排除する。
また、Dの辺は常に自由なのでまとめて計算できる。
それを加味してパターン分けしたのが以下である。

パターン1・・・B及びCの辺を、どちらも頂点Nに繋げないとする。
すると、Aの辺については自由に動かせる。
(初期グラフで既に0と1が繋がっている事が条件だが)

パターン2・・・Bの辺を頂点Nに繋げるとする。
すると、Aの辺を頂点Nに繋げる必要がでてくる。

パターン3・・・Cの辺を頂点Nに繋げるとする。
すると、Aの辺を頂点Nに繋げる必要がでてくる。

パターン4・・・BおよびCの辺を頂点Nに繋げるとする。
すると、Aの辺については自由に動かせる。

※Dは常に自由に動かせる。

事後

これほんとEasyなの?ん?どうなの?Medじゃないの?

ソースコード

class Sunnygraphs {
    public:
    long long count(vector<int> _a) {

        a = _a;
        n = a.size();

        // 有効グラフ作成
        createGreph();

        // 0,1それぞれでつながる所を算出
        findReach0();
        findReach1();

        // 0,1から到達する頂点
        // 0からのみ到達する頂点
        // 1からのみ到達する頂点
        // 0,1から到達しない頂点
        // ・・・を数える
        int r01 = 0;
        int r0 = 0;
        int r1 = 0;
        int nr = 0;
        for (int i = 0; i < n; i++) {
            if (reach0[i]) {
                if (reach1[i]) {
                    r01++;
                } else {
                    r0++;
                }
            } else {
                if (reach1[i]) {
                    r1++;
                } else {
                    nr++;
                }
            }
        }

        long long ans = 0;
        // パターン1
        if (r01 >= 1) {
            ans += pow2(r01);
        }

        // パターン2
        ans += (pow2(r0) - 1) * (pow2(r01) - 1);

        // パターン3
        ans += (pow2(r1) - 1) * (pow2(r01) - 1);

        // パターン4
        ans += (pow2(r0) - 1) * (pow2(r1) - 1) * (pow2(r01));

        // 0および1から到達しない頂点は自由
        ans *= (pow2(nr));

        return ans;
    }

    void createGreph() {
        for (int i = 0; i <= n; i++) {
            g[i].clear();
        }

        for (int i = 0; i < n; i++) {
            g[i].push_back(a[i]);
        }
    }

    void findReach0() {
        for (int i = 0; i < n; i++) {
            reach0[i] = false;
        }

        dfs0(0);
    }

    void dfs0(int cur) {
        reach0[cur] = true;

        for (int i = 0; i < g[cur].size(); i++) {
            if (reach0[g[cur][i]]) continue;
            dfs0(g[cur][i]);
        }
    }

    void findReach1() {
        for (int i = 0; i < n; i++) {
            reach1[i] = false;
        }

        dfs1(1);
    }

    void dfs1(int cur) {
        reach1[cur] = true;

        for (int i = 0; i < g[cur].size(); i++) {
            if (reach1[g[cur][i]]) continue;
            dfs1(g[cur][i]);
        }
    }

    long long pow2(int p) {
        long long res = 1;
        for (int i = 0; i < p; i++) {
            res *= 2;
        }
        return res;
    }
};