結果
| 問題 | No.1244 Black Segment |
| ユーザー |
 kuhaku
|
| 提出日時 | 2023-09-17 13:42:24 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 59 ms / 2,000 ms |
| コード長 | 9,680 bytes |
| コンパイル時間 | 3,766 ms |
| コンパイル使用メモリ | 238,640 KB |
| 実行使用メモリ | 14,668 KB |
| 最終ジャッジ日時 | 2024-07-04 09:10:15 |
| 合計ジャッジ時間 | 6,897 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 2 ms
6,940 KB |
| testcase_02 | AC | 1 ms
6,944 KB |
| testcase_03 | AC | 2 ms
6,944 KB |
| testcase_04 | AC | 1 ms
6,940 KB |
| testcase_05 | AC | 2 ms
6,944 KB |
| testcase_06 | AC | 1 ms
6,940 KB |
| testcase_07 | AC | 2 ms
6,944 KB |
| testcase_08 | AC | 1 ms
6,940 KB |
| testcase_09 | AC | 2 ms
6,940 KB |
| testcase_10 | AC | 2 ms
6,944 KB |
| testcase_11 | AC | 2 ms
6,940 KB |
| testcase_12 | AC | 2 ms
6,944 KB |
| testcase_13 | AC | 3 ms
6,940 KB |
| testcase_14 | AC | 24 ms
7,296 KB |
| testcase_15 | AC | 3 ms
6,944 KB |
| testcase_16 | AC | 24 ms
7,168 KB |
| testcase_17 | AC | 3 ms
6,944 KB |
| testcase_18 | AC | 31 ms
9,472 KB |
| testcase_19 | AC | 44 ms
10,824 KB |
| testcase_20 | AC | 45 ms
11,136 KB |
| testcase_21 | AC | 36 ms
10,720 KB |
| testcase_22 | AC | 44 ms
10,752 KB |
| testcase_23 | AC | 45 ms
10,960 KB |
| testcase_24 | AC | 47 ms
11,392 KB |
| testcase_25 | AC | 45 ms
11,584 KB |
| testcase_26 | AC | 43 ms
10,584 KB |
| testcase_27 | AC | 39 ms
8,832 KB |
| testcase_28 | AC | 45 ms
11,264 KB |
| testcase_29 | AC | 41 ms
10,368 KB |
| testcase_30 | AC | 45 ms
11,728 KB |
| testcase_31 | AC | 41 ms
10,496 KB |
| testcase_32 | AC | 42 ms
10,240 KB |
| testcase_33 | AC | 42 ms
10,496 KB |
| testcase_34 | AC | 59 ms
14,668 KB |
| testcase_35 | AC | 49 ms
14,616 KB |
| testcase_36 | AC | 45 ms
13,176 KB |
| testcase_37 | AC | 51 ms
12,672 KB |
| testcase_38 | AC | 51 ms
12,156 KB |
ソースコード
#line 1 "a.cpp"
#define PROBLEM ""
#line 2 "/home/kuhaku/atcoder/github/algo/lib/template/template.hpp"
#pragma GCC target("sse4.2,avx2,bmi2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
template <class T, class U>
bool chmax(T &a, const U &b) {
return a < (T)b ? a = (T)b, true : false;
}
template <class T, class U>
bool chmin(T &a, const U &b) {
return (T)b < a ? a = (T)b, true : false;
}
constexpr std::int64_t INF = 1000000000000000003;
constexpr int Inf = 1000000003;
constexpr int MOD = 1000000007;
constexpr int MOD_N = 998244353;
constexpr double EPS = 1e-7;
constexpr double PI = M_PI;
#line 3 "/home/kuhaku/atcoder/github/algo/lib/graph/graph.hpp"
/**
* @brief 重み付きグラフ
*
* @tparam T 辺の重みの型
*/
template <class T>
struct Graph {
private:
struct _edge {
constexpr _edge() : _from(), _to(), _weight() {}
constexpr _edge(int from, int to, T weight) : _from(from), _to(to), _weight(weight) {}
constexpr bool operator<(const _edge &rhs) const { return this->weight() < rhs.weight(); }
constexpr bool operator>(const _edge &rhs) const { return rhs < *this; }
constexpr int from() const { return this->_from; }
constexpr int to() const { return this->_to; }
constexpr T weight() const { return this->_weight; }
private:
int _from, _to;
T _weight;
};
public:
using edge_type = typename Graph<T>::_edge;
Graph() : _size(), edges() {}
Graph(int v) : _size(v), edges(v) {}
const auto &operator[](int i) const { return this->edges[i]; }
auto &operator[](int i) { return this->edges[i]; }
const auto begin() const { return this->edges.begin(); }
auto begin() { return this->edges.begin(); }
const auto end() const { return this->edges.end(); }
auto end() { return this->edges.end(); }
constexpr int size() const { return this->_size; }
void add_edge(const edge_type &e) { this->edges[e.from()].emplace_back(e); }
void add_edge(int from, int to, T weight = T(1)) {
this->edges[from].emplace_back(from, to, weight);
}
void add_edges(int from, int to, T weight = T(1)) {
this->edges[from].emplace_back(from, to, weight);
this->edges[to].emplace_back(to, from, weight);
}
void input_edge(int m, int base = 1) {
for (int i = 0; i < m; ++i) {
int from, to;
T weight;
std::cin >> from >> to >> weight;
this->add_edge(from - base, to - base, weight);
}
}
void input_edges(int m, int base = 1) {
for (int i = 0; i < m; ++i) {
int from, to;
T weight;
std::cin >> from >> to >> weight;
this->add_edges(from - base, to - base, weight);
}
}
private:
int _size;
std::vector<std::vector<edge_type>> edges;
};
template <>
struct Graph<void> {
private:
struct _edge {
constexpr _edge() : _from(), _to() {}
constexpr _edge(int from, int to) : _from(from), _to(to) {}
constexpr int from() const { return this->_from; }
constexpr int to() const { return this->_to; }
constexpr int weight() const { return 1; }
constexpr bool operator<(const _edge &rhs) const { return this->weight() < rhs.weight(); }
constexpr bool operator>(const _edge &rhs) const { return rhs < *this; }
private:
int _from, _to;
};
public:
using edge_type = typename Graph<void>::_edge;
Graph() : _size(), edges() {}
Graph(int v) : _size(v), edges(v) {}
const auto &operator[](int i) const { return this->edges[i]; }
auto &operator[](int i) { return this->edges[i]; }
const auto begin() const { return this->edges.begin(); }
auto begin() { return this->edges.begin(); }
const auto end() const { return this->edges.end(); }
auto end() { return this->edges.end(); }
constexpr int size() const { return this->_size; }
void add_edge(const edge_type &e) { this->edges[e.from()].emplace_back(e); }
void add_edge(int from, int to) { this->edges[from].emplace_back(from, to); }
void add_edges(int from, int to) {
this->edges[from].emplace_back(from, to);
this->edges[to].emplace_back(to, from);
}
void input_edge(int m, int base = 1) {
for (int i = 0; i < m; ++i) {
int from, to;
std::cin >> from >> to;
this->add_edge(from - base, to - base);
}
}
void input_edges(int m, int base = 1) {
for (int i = 0; i < m; ++i) {
int from, to;
std::cin >> from >> to;
this->add_edges(from - base, to - base);
}
}
private:
int _size;
std::vector<std::vector<edge_type>> edges;
};
#line 4 "/home/kuhaku/atcoder/github/algo/lib/graph/dijkstra.hpp"
/**
* @brief ダイクストラ法
*
* @tparam T 辺の重みの型
* @param g グラフ
* @param s 始点
* @param inf 正の無限表現
* @retval std::vector<T> 各頂点までの最短距離
*/
template <class T>
std::vector<T> dijkstra(const Graph<T> &g, int s = 0, T inf = std::numeric_limits<T>::max()) {
struct _node {
constexpr _node() : _to(), _dist() {}
constexpr _node(int to, T dist) : _to(to), _dist(dist) {}
constexpr bool operator<(const _node &rhs) const { return this->dist() < rhs.dist(); }
constexpr bool operator>(const _node &rhs) const { return rhs < *this; }
constexpr int to() const { return this->_to; }
constexpr T dist() const { return this->_dist; }
private:
int _to;
T _dist;
};
std::vector<T> dists(g.size(), inf);
std::priority_queue<_node, std::vector<_node>, std::greater<>> p_que;
dists[s] = T();
p_que.emplace(s, T());
while (!p_que.empty()) {
auto node = p_que.top();
p_que.pop();
if (dists[node.to()] < node.dist()) continue;
for (auto &e : g[node.to()]) {
if (chmin(dists[e.to()], node.dist() + e.weight()))
p_que.emplace(e.to(), node.dist() + e.weight());
}
}
return dists;
}
std::vector<int> dijkstra(const Graph<void> &g, int s = 0,
int inf = std::numeric_limits<int>::max()) {
std::vector<int> dists(g.size(), inf);
std::queue<int> que;
dists[s] = 0;
que.emplace(s);
while (!que.empty()) {
auto index = que.front();
que.pop();
for (auto &e : g[index]) {
if (chmin(dists[e.to()], dists[index] + 1)) que.emplace(e.to());
}
}
return dists;
}
#line 3 "/home/kuhaku/atcoder/github/algo/lib/template/macro.hpp"
#define FOR(i, m, n) for (int i = (m); i < int(n); ++i)
#define FORR(i, m, n) for (int i = (m)-1; i >= int(n); --i)
#define FORL(i, m, n) for (int64_t i = (m); i < int64_t(n); ++i)
#define rep(i, n) FOR (i, 0, n)
#define repn(i, n) FOR (i, 1, n + 1)
#define repr(i, n) FORR (i, n, 0)
#define repnr(i, n) FORR (i, n + 1, 1)
#define all(s) (s).begin(), (s).end()
#line 3 "/home/kuhaku/atcoder/github/algo/lib/template/sonic.hpp"
struct Sonic {
Sonic() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
}
constexpr void operator()() const {}
} sonic;
#line 5 "/home/kuhaku/atcoder/github/algo/lib/template/atcoder.hpp"
using namespace std;
using ll = std::int64_t;
using ld = long double;
template <class T, class U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
return is >> p.first >> p.second;
}
template <class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
for (T &i : v) is >> i;
return is;
}
template <class T, class U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) {
return os << '(' << p.first << ',' << p.second << ')';
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
for (auto it = v.begin(); it != v.end(); ++it) {
os << (it == v.begin() ? "" : " ") << *it;
}
return os;
}
template <class Head, class... Tail>
void co(Head &&head, Tail &&...tail) {
if constexpr (sizeof...(tail) == 0) std::cout << head << '\n';
else std::cout << head << ' ', co(std::forward<Tail>(tail)...);
}
template <class Head, class... Tail>
void ce(Head &&head, Tail &&...tail) {
if constexpr (sizeof...(tail) == 0) std::cerr << head << '\n';
else std::cerr << head << ' ', ce(std::forward<Tail>(tail)...);
}
template <typename T, typename... Args>
auto make_vector(T x, int arg, Args... args) {
if constexpr (sizeof...(args) == 0) return std::vector<T>(arg, x);
else return std::vector(arg, make_vector<T>(x, args...));
}
void setp(int n) {
std::cout << std::fixed << std::setprecision(n);
}
void Yes(bool is_correct = true) {
std::cout << (is_correct ? "Yes" : "No") << '\n';
}
void No(bool is_not_correct = true) {
Yes(!is_not_correct);
}
void YES(bool is_correct = true) {
std::cout << (is_correct ? "YES" : "NO") << '\n';
}
void NO(bool is_not_correct = true) {
YES(!is_not_correct);
}
void Takahashi(bool is_correct = true) {
std::cout << (is_correct ? "Takahashi" : "Aoki") << '\n';
}
void Aoki(bool is_not_correct = true) {
Takahashi(!is_not_correct);
}
#line 4 "a.cpp"
int main(void) {
int n, m, a, b;
cin >> n >> m >> a >> b;
--a;
Graph<int> g(n + 1);
while (m--) {
int u, v;
cin >> u >> v;
g.add_edges(u - 1, v, 1);
}
rep (i, a) g.add_edges(i, a, 0);
FOR (i, b + 1, n + 1) g.add_edges(b, i, 0);
int ans = dijkstra(g, a, Inf)[b];
co(ans == Inf ? -1 : ans);
return 0;
}