mapは遅い場合があるのでsetやunorderedを検討する

対象の問題

https://atcoder.jp/contests/joi2007ho/tasks/joi2007ho_c

atcoder.jp

略解

2頂点決まれば、あともう2頂点の座標は計算で出せるので、そういう2頂点が存在するかを調べれば良い。 したがって、2頂点の存在を適切なデータ構造で確認すれば で解ける

適切なデータ構造 として map<pair<int, int>> を選んだが、これだとTLEだった

解決方法

set や unordered_set を使う。map よりも高速に動作する。 特に unordered_set は格納順が規定されていないためより高速。

qiita.com

以下メモ的コード例です

// 要素の追加
mp[Key] = 1;      // map
st.insert(Key);   // set
u_ut.insert(Key); // unordered_set

// 要素が存在するか
if (mp[Key] == 1) { ... }
if (st.find(Key) != st.end()) { ... }
if (u_st.find(Key) != u_st.end()) { ... }

ただし、 unorderd_set<pair<int, int>> などはエラーが出るため以下のように解決する （参考: std::unordered_setはデフォルトではpairが使えない[自分用メモ] - Qiita）

struct phash {
    inline size_t operator ()(const pair<int,int>& p) const {
        const auto h1 = hash<int>()(p.first);
        const auto h2 = hash<int>()(p.second);
        return h1 ^ (h2 << 1);
    }
};

int main() {
    unordered_set<pair<int, int>, phash> u_set;
}

同じ失敗を繰り返さないために

map<Key, bool> と定義したくなったら set や unordered_set を検討する

• 特にソートされている必要がないなら unorderd_set を検討する

参考

正答コード

atcoder.jp