今日も解いた問題の解説をします。問題はこちら。
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を使いましょう。)
コメント