【競プロ】1日1AC : ABC68 C問題 Cat Snuke and a Voyage

今日も解いた問題の解説をします。問題はこちら。

Diffは579（茶）です。

提出コードと考え方

別解は色々考えられますが、自分が解いた方法で説明します。

島 \(1,i\) を結ぶ定期船と、島 \(i,N\) を結ぶ定期船が存在すれば「POSSIBLE」となります。

ここで「島 \(1\) から島 \(i\) へ移動できるか」を配列 \(data\) で持ちます。ここでは定期船の数をint型で持っておきます。（定期船は重複なしなので値は最大でも \(1\) ですが。）

この配列に値を記憶し終えたら、再度ループを回します。

見ている定期船が島 \(N\) に到着する時、出発する島を \(a_i\) として \(data[a_i]\) の値をチェックすることで、島 \(1,a_i\) 間、島 \(a_i,N\) 間を移動できるか判定できます。

以下が提出コードです。

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> a(m),b(m);
    vector<int> data(200001,0);
    bool flag = false;
    rep(i,m){
        cin >> a[i] >> b[i];
        if(a[i] == 1) data[b[i]]++;
    }
    rep(i,m){
        if(b[i] == n && data[a[i]] > 0) flag = true;
    }
    if(flag) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;
}

ちなみにcin, coutは遅いです。入力が多い場合は

cin.tie(0); 
ios::sync_with_stdio(false);

をmain関数に書くと、実行時間が短くなります。（あるいはscanf, printfを使いましょう。）