結果
問題 | No.1983 [Cherry 4th Tune C] 南の島のマーメイド |
ユーザー |
|
提出日時 | 2022-08-29 03:26:34 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 657 ms / 4,000 ms |
コード長 | 1,264 bytes |
コンパイル時間 | 8,045 ms |
コンパイル使用メモリ | 360,872 KB |
実行使用メモリ | 51,024 KB |
最終ジャッジ日時 | 2024-11-06 03:42:36 |
合計ジャッジ時間 | 26,866 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 41 |
ソースコード
#include <bits/extc++.h> #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; #endif #define rep(i, n) for (int i = 0; i < (n); ++i) using std::cin; using std::cout; using std::min; using std::vector; using std::function; int main() { int n, m, q; cin >> n >> m >> q; vector<vector<int>> to(n); rep(i, m) { int a, b; cin >> a >> b; --a; --b; to[a].push_back(b); to[b].push_back(a); } vector<int> ord(n, n); vector<int> low(n, n); dsu t(n); int id = 0; function<void(int, int)> tarjan = [&](int v, int p) { ord[v] = low[v] = id++; for (int u : to[v]) { if (u == p) continue; if (ord[u] == n) { tarjan(u, v); low[v] = min(low[v], low[u]); if (ord[v] < low[u]) { t.merge(v, u); } } else { low[v] = min(low[v], ord[u]); } } }; rep(i, n) { if (ord[i] == n) tarjan(i, n); } rep(qi, q) { int a, b; cin >> a >> b; --a; --b; if (t.same(a, b)) puts("Yes"); else puts("No"); } return 0; }