結果

問題 No.1244 Black Segment
ユーザー pazzle1230pazzle1230
提出日時 2020-10-02 21:55:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 52 ms / 2,000 ms
コード長 3,570 bytes
コンパイル時間 1,642 ms
コンパイル使用メモリ 178,608 KB
実行使用メモリ 11,928 KB
最終ジャッジ日時 2024-07-16 04:56:13
合計ジャッジ時間 3,949 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
	for(auto &e:u) fill_v<T>(e,v...);
}

template<typename W>
struct range_edge_graph {
  int n;
  struct edge { int to; W weight;};
  vector<vector<edge>> g;

  range_edge_graph(int n) : n(n) {
    g.resize(4*n);
    for (int i = 1; i < n; ++i) {
      int cl = i<<1|0, cr = i<<1|1;
      g[i].push_back({cl, 0});
      g[i].push_back({cr, 0});
      g[cl+2*n].push_back({i+2*n, 0});
      g[cr+2*n].push_back({i+2*n, 0});
    }
    for (int i = n; i < 2*n; ++i) g[i].push_back({i+2*n, 0});
  }

  // from [l1, r1) to [l2, r2)
  void add_edge(int l1, int r1, int l2, int r2, W w) {
    int idx = g.size();
    for (l1 += n, r1 += n; l1 < r1; l1 >>= 1, r1 >>= 1) {
      if (l1 & 1) g[l1+2*n].push_back({idx, 0}), l1++;
      if (r1 & 1) --r1, g[r1+2*n].push_back({idx, 0});
    }
    vector<edge> node;
    for (l2 += n, r2 += n; l2 < r2; l2 >>= 1, r2 >>= 1) {
      if (l2 & 1) node.push_back({l2++, w});
      if (r2 & 1) node.push_back({--r2, w});
    }
    g.push_back(node);
  }

  vector<W> dijkstra(int s) {
    s += n;
    vector<W> dist(g.size(), numeric_limits<W>::max());
    dist[s] = 0;
    using P = pair<W, int>;
    priority_queue<P, vector<P>, greater<P>> que;
    que.emplace(0, s);
    while (!que.empty()) {
      P p = que.top();
      que.pop();
      int v = p.second;
      if (dist[v] < p.first) continue;
      for (edge& e : g[v]) {
        if (dist[e.to] > dist[v] + e.weight) {
          dist[e.to] = dist[v] + e.weight;
          que.emplace(dist[e.to], e.to);
        }
      }
    }
    vector<W> res(dist.begin() + n, dist.begin() + 2*n);
    return res;
  }
};

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int64 N, M, A, B;
  cin >> N >> M >> A >> B; A--;

  vector<int64> G[112345];

  REP(i, M) {
    int64 L, R;
    cin >> L >> R; L--; R--;
    G[L].push_back(R+1);
    G[R+1].push_back(L);
    if (A+1 == B && L == A && R+1 == B) {
      cout << 1 << endl;
      return 0;
    }
  }

  vector<int64> d(N+1, INF_LL);
  priority_queue<PLL, vector<PLL>, greater<PLL>> pq;
  REP(i, A+1) {
    pq.emplace(0, i);
    d[i] = 0;
  }

  while (pq.size()) {
    int64 vv, dd;
    tie(dd, vv) = pq.top(); pq.pop();
    if (dd > d[vv]) continue;
    for (auto &u : G[vv]) {
      if (dd + 1 < d[u]) {
        d[u] = dd + 1;
        pq.emplace(dd + 1, u);
      }
    }
  }
  int64 res = INF_LL;
  FOR(i, B, N+1) {
    chmin(res, d[i]);
  }
  if (res == INF_LL) {
    cout << -1 << endl;
  } else {
    cout << res << endl;
  }
}
0