SRM658 Div1 Easy "OddEvenTree"
考えたこと
グラフは木ということで、Simple Pathの長さ(距離)には、以下のような性質があるっぽい。
まず、隣のノードは違う色になるように赤青2色で塗り分ける。
すると、赤と赤もしくは青と青のノード同士は必ず距離が偶数になり、
赤と青のノードは同士は必ず距離が奇数になる。
これより、距離の偶奇で考えた時、距離が偶数のノード同士が仲間とする「2つのお仲間グループ」ができる。
・・・
今回の問題では、インパラでもらう情報が上の性質と矛盾していないかを調べればよさそう。
サンプル通った。Submitポチー
撃 沈
事後
インパラが
EE
EE
とか、1つの木として繋がっていないパターンを考慮できていなかった。。。
ソースコード
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) { // 1つの木じゃない! ans.clear(); ans.push_back(-1); } return ans; } } };