結果

問題 No.1244 Black Segment
ユーザー pazzle1230pazzle1230
提出日時 2020-10-02 21:55:56
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 63 ms / 2,000 ms
コード長 3,570 bytes
コンパイル時間 1,705 ms
コンパイル使用メモリ 176,816 KB
実行使用メモリ 11,752 KB
最終ジャッジ日時 2023-09-23 04:53:52
合計ジャッジ時間 4,621 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,004 KB
testcase_01 AC 4 ms
6,012 KB
testcase_02 AC 3 ms
6,012 KB
testcase_03 AC 3 ms
6,016 KB
testcase_04 AC 4 ms
6,084 KB
testcase_05 AC 4 ms
6,064 KB
testcase_06 AC 3 ms
6,032 KB
testcase_07 AC 4 ms
6,080 KB
testcase_08 AC 3 ms
5,960 KB
testcase_09 AC 4 ms
5,976 KB
testcase_10 AC 3 ms
5,944 KB
testcase_11 AC 3 ms
6,008 KB
testcase_12 AC 3 ms
6,028 KB
testcase_13 AC 4 ms
6,176 KB
testcase_14 AC 25 ms
8,704 KB
testcase_15 AC 5 ms
6,120 KB
testcase_16 AC 25 ms
8,644 KB
testcase_17 AC 5 ms
6,192 KB
testcase_18 AC 37 ms
8,768 KB
testcase_19 AC 51 ms
10,200 KB
testcase_20 AC 55 ms
10,208 KB
testcase_21 AC 43 ms
9,980 KB
testcase_22 AC 55 ms
10,240 KB
testcase_23 AC 58 ms
10,188 KB
testcase_24 AC 52 ms
10,556 KB
testcase_25 AC 53 ms
10,420 KB
testcase_26 AC 51 ms
9,688 KB
testcase_27 AC 46 ms
9,588 KB
testcase_28 AC 57 ms
10,588 KB
testcase_29 AC 50 ms
10,196 KB
testcase_30 AC 56 ms
10,404 KB
testcase_31 AC 48 ms
10,108 KB
testcase_32 AC 48 ms
10,148 KB
testcase_33 AC 48 ms
9,872 KB
testcase_34 AC 60 ms
10,688 KB
testcase_35 AC 51 ms
10,724 KB
testcase_36 AC 48 ms
10,664 KB
testcase_37 AC 63 ms
11,752 KB
testcase_38 AC 51 ms
11,180 KB
権限があれば一括ダウンロードができます

ソースコード

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