ABC-068 C Cat Snuke and a Voyage を解いてみた

今回の問題もデータ構造に関する問題でした。基本的に問題の解き方はグラフを作りダイクストラあたりで解くか、1 ~ Nまでの経路が存在するかのデータ構造を構築するあたりが妥当でした． ハッシュ的に解く想定はできたのですがTLEとWAで，なかなかACできず苦労しました． では以下問題文

問題

Cat Snuke and a Voyage

高橋キングダムには、高橋諸島という、N 個の島からなる諸島があります。 便宜上、これらの島を島 1、島2、 ...、島 N と呼ぶことにします。

これらの諸島の間では、船の定期便が M 種類運行されています。 定期便はそれぞれ 2 つの島の間を行き来しており i 種類目の定期便を使うと、 島 aiと島 bi の間を行き来する事ができます。

すぬけくんは今島 1 にいて、島 N に行きたいと思っています。 しかし、島 1 から島 N への定期便は存在しないことがわかりました。 なので、定期便を 2 つ使うことで、島 N に行けるか調べたいと思っています。

これを代わりに調べてあげてください。

制約

  • 3≦N≦200,000
  • 1≦M≦200,000
  • 1≦ai<bi≦N
  • (ai,bi)≠(1,N)i≠j ならば (ai,bi)≠(aj,bj)

とこんな感じ

考えたこと

出発点と目的地が決まっていれば、計算する部分は1 ~ i と i ~ Nということがわかります。つまり全探索前に全探索ができるようにデータ構造をつくれるかどうかが鍵になってくるなと考えました。

入力を受け取りながら出発地が1の時に目的地の場所をハッシュで保持し、その要素を真にします。その次にNが目的地の時に出発地の場所にハッシュで保持し、その要素を真にする。

この操作はO(M)の操作で終わります 次に全探索を行いNまでの経路があるかを洗い出します。

フロー

  • 入力の受け取りN,M
  • 2つの配列を宣言し配列の中身を初期化
  • 制約外なら終了
  • 定期便の入力を受け取りながら以下の処理をする
    • 出発地と目的地の受け取り
    • もし出発地が1の時に片方の配列の目的地の要素を真にする
    • もし目的地がNの時に片方の配列の出発地の要素を真にする
  • 各島(N)に対して以下の処理を行う
    • もしその島が目的地かつNへの出発地ならばPOSSIBLEと出力
    • 終了
  • IMPOSSIBLEと出力
  • 終了

みたいな感じになりました 全探索の際は定期便の中心となるNがループの主体になります。

プログラム

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
using namespace std;

int main(void){
    int N , M;
    cin >> N >> M;
    vector<bool> a(200000);
    vector<bool> b(200000);
    for (int i = 0;i < 200000; i++){
        a[i] = 0;
        b[i] = 0;
    }
    if (N < 3 && N > 200000 && 1 > M && M > 200000){
        return 0;
    }
    for (int i = 0;i < M; i++){
        long long from,to;
        cin >> from >> to;
        if(from == 1){
            a[to] = true;
        }
        if(to == N){
            b[from] = true;
        }
    }
    for (int i = 0;i < N; i++){
        if(a[i] && b[i]){
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;

    return 0;
}

これでAC取れました