SRM658 Div1 Easy "OddEvenTree"

問題

TopCoder Statistics - Problem Statement

考えたこと

グラフは木ということで、Simple Pathの長さ(距離)には、以下のような性質があるっぽい。

まず、隣のノードは違う色になるように赤青２色で塗り分ける。

すると、赤と赤もしくは青と青のノード同士は必ず距離が偶数になり、
赤と青のノードは同士は必ず距離が奇数になる。
これより、距離の偶奇で考えた時、距離が偶数のノード同士が仲間とする「２つのお仲間グループ」ができる。

・・・

今回の問題では、インパラでもらう情報が上の性質と矛盾していないかを調べればよさそう。

サンプル通った。Submitポチー

撃　沈

事後

インパラが
EE
EE
とか、１つの木として繋がっていないパターンを考慮できていなかった。。。

ソースコード

class OddEvenTree {
public:

    int n;
    int type[55];

    vector <int> getTree(vector <string> x) {

        n = x.size();

        for (int i = 0; i < n; i++) {
            type[i] = 0;
        }

        // 矛盾がないか探す
        bool ret = true;
        
        for (int i = 0; i < n; i++) {
            if (i == 0) type[i] = 1;
            for (int j = 0; j < n; j++) {
                // 仲間
                if (x[i][j] == 'E') {
                    // 仲間じゃない！(矛盾)
                    if (type[j] == -type[i]) {
                        ret = false;
                    }
                    // よかった
                    else {
                        type[j] = type[i];
                    }
                } 
                // 仲間じゃない
                else {
                    // 仲間！(矛盾)
                    if (type[j] == type[i]) {
                        ret = false;
                    }
                    // よかった
                    else {
                        type[j] = -type[i];
                    }
                }
            }
        }

        // 答え作成
        vector <int> ans;

        // 矛盾があれば-1
        if (!ret) {
            ans.push_back(-1);
            return ans;
        }
        // 矛盾なし
        else {
            for (int i = 1; i < n; i++) {
                bool ok = false;
                for (int j = 0; j < n; j++) {
                    if (x[i][j] == 'O') {
                        ans.push_back(i);
                        ans.push_back(j);
                        ok = true;
                    }
                    if (ok) break;
                }
            }
            if (ans.size() != (n - 1) * 2) {
                // １つの木じゃない！
                ans.clear();
                ans.push_back(-1);
            }
            return ans;
        }        
    }
};