Submission #66070

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
#include <bits/stdc++.h>
// header {{{
/**
* @brief all()マクロ
*/
#define all(x) std::begin(x), std::end(x)
#define rall(x) std::rbegin(x), std::rend(x)
/**
* @brief rep()マクロ
*/
#define rep(i, begin, end) for (int64_t i = (begin), i##_end = (end); i < i##_end; ++i)
#define repc(i, begin, last) for (int64_t i = (begin), i##_last = (last); i <= i##_last; ++i)
#define repr(i, begin, last) for (int64_t i = (begin), i##_last = (last); i >= i##_last; --i)
#define let const auto
/**
* @brief int-alias (整数型のエイリアス)
*/
using i64 = int64_t;
using u64 = uint64_t;
/**
* @brief int-infinity (整数のデカイ値)
* 2倍してもオーバーフローしない & memset()にも使える (需要ある？)
*/
constexpr int32_t INF = 0x3f3f3f3f;
constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
/**
* @brief read() (n個入力してContainerに格納して返す)
*/
template <class T = int, template <class, class...> class Container = std::vector>
Container<T> read(size_t n) {
Container<T> ret(n);
for (auto& e : ret) std::cin >> e;
return ret;
}
/**
* @brief std::ostreamによるコンテナの出力
*/
template <class Container, class = typename Container::value_type, std::enable_if_t<!std::is_same<Container, std::string>::value, std::nullptr_t> = nullptr>
std::ostream& operator<<(std::ostream& os, const Container& v) {
for (auto it = std::begin(v); it != std::end(v); ++it) os << &" "[it == std::begin(v)] << *it;
return os;
}
/**
* @brief 複数変数宣言をして同時に入力もするやつ
*/
template <class T>
std::istream& operator,(std::istream& is, T& rhs) {
return is >> rhs;
}
#define var(type, ...) \
type __VA_ARGS__; \
std::cin >> __VA_ARGS__
/**
* @brief println() (可変個の値を空白区切りで出力して改行する)
*/
inline void println() {
std::cout << '\n';
}
template <class Head, class... Tail>
inline void println(Head&& head, Tail&&... tail) {
std::cout << head << &" "[!sizeof...(tail)];
println(std::forward<Tail>(tail)...);
}
/**
* @brief chmin(), chmax()
*/
template <class T, class U>
inline bool chmin(T& a, const U& b) {
return b < a && (a = b, true);
}
template <class T, class U>
inline bool chmax(T& a, const U& b) {
return b > a && (a = b, true);
}
/**
* @brief makeVec() (多次元std::vectorの生成)
*/
template <class T>
inline std::vector<T> makeVec(size_t sz, const T& initValue) {
return std::vector<T>(sz, initValue);
}
template <class T, class... Args>
inline auto makeVec(size_t sz, Args... args) {
return std::vector<decltype(makeVec<T>(args...))>(sz, makeVec<T>(args...));
}
// }}}
// debug {{{
/**
* @brief Debug
*/
#ifdef LOCAL_DEBUG
namespace dbg {
int w_ = 4;
bool negativeValAsNull_ = true;
std::ostream* os = &std::cerr;
template <class T, std::enable_if_t<!std::is_arithmetic<T>::value, std::nullptr_t> = nullptr>
void put(const T& x) {
*os << std::setw(w_) << x;
}
template <class T, std::enable_if_t<std::is_signed<T>::value, std::nullptr_t> = nullptr>
void put(const T& x) {
if (x <= -INF)
*os << std::setw(w_) << "-INF";
else if (negativeValAsNull_ && x < 0)
*os << std::setw(w_) << " - ";
else if (x >= INF)
*os << std::setw(w_) << "INF";
else
*os << std::setw(w_) << x;
}
template <class T, std::enable_if_t<std::is_unsigned<T>::value, std::nullptr_t> = nullptr>
void put(const T& x) {
if (static_cast<int64_t>(x) >= static_cast<int64_t>(INF))
*os << std::setw(w_) << "INF";
else
*os << std::setw(w_) << x;
}
template <class A, class B>
void put(const std::pair<A, B>& t) {
*os << '(' << std::setw(w_) << std::get<0>(t) << ", " << std::setw(w_) << std::get<1>(t) << ')';
}
template <class A, class B, class C>
void put(const std::tuple<A, B, C>& t) {
*os << '(' << std::setw(w_) << std::get<0>(t) << ", " << std::setw(w_) << std::get<1>(t) << ", " << std::setw(w_) << std::get<2>(t) << ')';
}
template <class Arr>
void showArrayH__(const Arr& a, size_t begin, size_t end) {
for (size_t i = begin; i < end; ++i) *os << '[' << std::setw(dbg::w_) << i << "] ";
*os << '\n';
for (size_t i = begin; i < end; ++i) *os << ' ', dbg::put(a[i]), *os << " ";
*os << '\n';
}
template <class Arr>
void showArrayV__(const Arr& a, size_t begin, size_t end) {
for (size_t i = begin; i < end; ++i)
*os << '[' << std::setw(2) << i << ']', dbg::put(a[i]), *os << "\n";
*os << std::flush;
}
template <class Table>
void showTable__(const Table& t, size_t yBegin, size_t yEnd, size_t xBegin, size_t xEnd) {
*os << std::string(1 + 2 + 1, ' ');
for (size_t j = xBegin; j < xEnd; ++j) *os << '[' << std::setw(dbg::w_) << j << "] ";
*os << '\n';
for (size_t i = yBegin; i < yEnd; ++i) {
*os << '[' << std::setw(2) << i << "]";
for (size_t j = xBegin; j < xEnd; ++j) *os << ' ', dbg::put(t[i][j]), *os << " ";
*os << '\n';
}
}
} // namespace dbg
void debug_setw(int w) {
dbg::w_ = w;
}
void debug_negativeValAsNull(bool f) {
dbg::negativeValAsNull_ = f;
}
void debug_setOstream(std::ostream& os) {
dbg::os = &os;
}
void debug_hr() {
*dbg::os << "----------------------------------------------------------------------\n";
}
void debug_println() {
*dbg::os << std::endl;
}
template <class Head, class... Tail>
void debug_println(const Head& head, const Tail&... tail) {
dbg::put(head);
debug_println(tail...);
}
#define putDbgPrefix() *dbg::os << __func__ << '(' << std::setfill('0') << std::setw(3) << __LINE__ << std::setfill(' ') << "): "
#define showArrayH(a, beginIdx, endIdx) (void)(putDbgPrefix() << #a << ":\n"), dbg::showArrayH__(a, beginIdx, endIdx)
#define showArrayV(a, beginIdx, endIdx) (void)(putDbgPrefix() << #a << ":\n"), dbg::showArrayV__(a, beginIdx, endIdx)
#define showTable(t, yBegin, yEnd, xBegin, xEnd) (void)(putDbgPrefix() << #t << ":\n"), dbg::showTable__(t, yBegin, yEnd, xBegin, xEnd)
#define dbgMsg_(x) " | " #x " = ", x
#define dump1(a) (void)(putDbgPrefix()), debug_println(#a " = ", a)
#define dump2(a, b) (void)(putDbgPrefix()), debug_println(#a " = ", a, dbgMsg_(b))
#define dump3(a, b, c) (void)(putDbgPrefix()), debug_println(#a " = ", a, dbgMsg_(b), dbgMsg_(c))
#define dump4(a, b, c, d) (void)(putDbgPrefix()), debug_println(#a " = ", a, dbgMsg_(b), dbgMsg_(c), dbgMsg_(d))
#define dump5(a, b, c, d, e) (void)(putDbgPrefix()), debug_println(#a " = ", a, dbgMsg_(b), dbgMsg_(c), dbgMsg_(d), dbgMsg_(e))
#define dump6(a, b, c, d, e, f) (void)(putDbgPrefix()), debug_println(#a " = ", a, dbgMsg_(b), dbgMsg_(c), dbgMsg_(d), dbgMsg_(e), dbgMsg_(f))
#define dump7(a, b, c, d, e, f, g) (void)(putDbgPrefix()), debug_println(#a " = ", a, dbgMsg_(b), dbgMsg_(c), dbgMsg_(d), dbgMsg_(e), dbgMsg_(f), dbgMsg_(g))
#define GET_8TH_ARG(dummy1, dummy2, dummy3, dummy4, dummy5, dummy6, dumy7, NAME, ...) NAME
#define dump(...) GET_8TH_ARG(__VA_ARGS__, dump7, dump6, dump5, dump4, dump3, dump2, dump1)(__VA_ARGS__)
#else
#define debug_setw(...) ((void)0)
#define debug_negativeValAsNull(...) ((void)0)
#define debug_setOstream(...) ((void)0)
#define debug_hr(...) ((void)0)
#define debug_println(...) ((void)0)
#define showArrayH(...) ((void)0)
#define showArrayV(...) ((void)0)
#define showTable(...) ((void)0)
#define dump(...) ((void)0)
#endif
// }}}
using namespace std;
// union-find {{{
/**
* @brief Union-Find (素集合データ構造)
* @note path-compression + union-by-size
*/
class UnionFind {
private:
int n;
mutable std::vector<int> p;
public:
UnionFind() = default;
explicit UnionFind(int n_)
: n(n_)
, p(n_, -1) {}
int unite(int x, int y) {
x = leader(x), y = leader(y);
if (x == y) return x;
if (p[y] < p[x]) std::swap(x, y);
p[x] += p[y];
p[y] = x;
return x;
}
int leader(int x) const { return p[x] < 0 ? x : p[x] = leader(p[x]); }
bool same(int x, int y) const { return leader(x) == leader(y); }
int size(int x) const { return -p[leader(x)]; }
std::vector<std::vector<int>> groups() const {
std::vector<int> leaderBuf(n), groupSize(n);
for (int i = 0; i < n; i++) ++groupSize[leaderBuf[i] = leader(i)];
std::vector<std::vector<int>> result(n);
for (int i = 0; i < n; i++) result[i].reserve(groupSize[i]);
for (int i = 0; i < n; i++) result[leaderBuf[i]].push_back(i);
result.erase(std::remove_if(result.begin(), result.end(), [](const std::vector<int>& v) { return v.empty(); }), result.end());
return result;
}
};
// }}}
const array<vector<int>, 2> bfs(const vector<vector<int>>& G, const int start) {
const auto N = G.size();
array<vector<int>, 2> dist{vector(N, INF), vector(N, INF)};
queue<pair<int, int>> que;
dist[0][start] = 0;
que.emplace(0, start);
while (que.size()) {
const auto [distMod2, cur] = que.front();
que.pop();
for (const int nxt : G[cur]) {
if (dist[1 - distMod2][nxt] < INF) continue;
dist[1 - distMod2][nxt] = dist[distMod2][cur] + 1;
que.emplace(1 - distMod2, nxt);
}
}
return dist;
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
var(int, N, M, X, Y);
--X, --Y;
UnionFind uf(N);
vector<vector<int>> G(N);
rep(i, 0, M) {
var(int, a, b);
--a, --b;
G[a].push_back(b);
G[b].push_back(a);
uf.unite(a, b);
}
assert(uf.size(0) == N);
const auto dist1 = bfs(G, X);
const auto dist2 = bfs(G, Y);
int ans = INF;
rep(u, 0, N) {
chmin(ans, max(dist1[0][u], dist2[0][u]));
chmin(ans, max(dist1[1][u], dist2[1][u]));
}
println(ans == INF ? -1 : ans);
return 0;
}

ステータス

項目 データ
問題 1359 - Encount
ユーザー名 syoribu
投稿日時 2021-04-06 14:51:04
言語 C++17
状態 Accepted
得点 4
ソースコード長 10136 Byte
最大実行時間 169 ms
最大メモリ使用量 17856 KB

セット

セット 得点 Cases
1 ALL 4 / 4 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 63 ms 4996 KB
1
in02.txt AC 60 ms 5556 KB
1
in03.txt AC 74 ms 7460 KB
1
in04.txt AC 39 ms 3288 KB
1
in05.txt AC 143 ms 15148 KB
1
in06.txt AC 141 ms 14608 KB
1
in07.txt AC 37 ms 4580 KB
1
in08.txt AC 136 ms 13936 KB
1
in09.txt AC 111 ms 12940 KB
1
in10.txt AC 63 ms 5296 KB
1
in11.txt AC 140 ms 15348 KB
1
in12.txt AC 71 ms 9400 KB
1
in13.txt AC 143 ms 15468 KB
1
in14.txt AC 136 ms 15336 KB
1
in15.txt AC 151 ms 15332 KB
1
in16.txt AC 166 ms 15340 KB
1
in17.txt AC 158 ms 15760 KB
1
in18.txt AC 151 ms 15268 KB
1
in19.txt AC 132 ms 15792 KB
1
in20.txt AC 129 ms 15896 KB
1
in21.txt AC 94 ms 11960 KB
1
in22.txt AC 45 ms 5420 KB
1
in23.txt AC 123 ms 15540 KB
1
in24.txt AC 122 ms 15476 KB
1
in25.txt AC 139 ms 15416 KB
1
in26.txt AC 129 ms 15356 KB
1
in27.txt AC 144 ms 15424 KB
1
in28.txt AC 136 ms 15368 KB
1
in29.txt AC 167 ms 15308 KB
1
in30.txt AC 156 ms 15380 KB
1
in31.txt AC 169 ms 15440 KB
1
in32.txt AC 62 ms 17824 KB
1
in33.txt AC 56 ms 17856 KB
1
in34.txt AC 19 ms 604 KB
1
in35.txt AC 27 ms 684 KB
1
in36.txt AC 39 ms 3452 KB
1
in37.txt AC 39 ms 3420 KB
1
sample01.txt AC 18 ms 604 KB
1
sample02.txt AC 25 ms 688 KB
1