Submission #1564979

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

int main()
{
  int N, M;
  cin >> N >> M;
  vector< int > ev[100];
  for(int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    ev[a].push_back(b + 1);
  }
  int dp[101];
  fill_n(dp, 101, INF);
  dp[0] = 0;
  for(int i = 0; i < N; i++) {
    for(auto &to : ev[i]) {
      for(int j = i + 1; j <= to; j++) {
        dp[j] = min(dp[j], dp[i] + 1);
      }
    }
  }

  if(dp[N] == INF) puts("Impossible");
  else cout << dp[N] << endl;
}

Submission Info

Judge Result