結果
問題 | No.2316 Freight Train |
ユーザー |
![]() |
提出日時 | 2024-04-07 00:32:49 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 464 ms / 2,000 ms |
コード長 | 2,499 bytes |
コンパイル時間 | 1,214 ms |
コンパイル使用メモリ | 121,524 KB |
実行使用メモリ | 7,040 KB |
最終ジャッジ日時 | 2024-10-01 04:15:57 |
合計ジャッジ時間 | 14,581 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#define _USE_MATH_DEFINES#include <iostream>#include <string>#include <algorithm>#include <vector>#include <queue>#include <math.h>#include <cmath>#include <stack>#include <map>#include <set>#include <numeric>#include <iomanip>#include <climits>#include <functional>#include <cassert>#include <tuple>using namespace std;using ll = long long;int N,Q;/// @brief Union-Find 木/// @note 1.2 グループの要素数取得対応/// @see https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/union-findclass UnionFind{public:UnionFind() = default;/// @brief Union-Find 木を構築します。/// @param n 要素数explicit UnionFind(size_t n): m_parents(n), m_sizes(n, 1){std::iota(m_parents.begin(), m_parents.end(), 0);}/// @brief 頂点 i の root のインデックスを返します。/// @param i 調べる頂点のインデックス/// @return 頂点 i の root のインデックスint find(int i){if (m_parents[i] == i){return i;}// 経路圧縮return (m_parents[i] = find(m_parents[i]));}/// @brief a のグループと b のグループを統合します。/// @param a 一方のインデックス/// @param b 他方のインデックスvoid merge(int a, int b){a = find(a);b = find(b);if (a != b){m_sizes[a] += m_sizes[b];m_parents[b] = a;}}/// @brief a と b が同じグループに属すかを返します。/// @param a 一方のインデックス/// @param b 他方のインデックス/// @return a と b が同じグループに属す場合 true, それ以外の場合は falsebool connected(int a, int b){return (find(a) == find(b));}/// @brief i が属するグループの要素数を返します。/// @param i インデックス/// @return i が属するグループの要素数int size(int i){return m_sizes[find(i)];}private:// m_parents[i] は i の 親,// root の場合は自身が親std::vector<int> m_parents;// グループの要素数 (root 用)// i が root のときのみ, m_sizes[i] はそのグループに属する要素数を表すstd::vector<int> m_sizes;};int main() {cin >> N >> Q;UnionFind uf(N+1);for(int i = 1; i <= N; ++i) {int p; cin >> p;if(p != -1) uf.merge(i,p);}while(Q--) {int a,b; cin >> a >> b;if(uf.connected(a,b)) cout << "Yes" << endl;else cout << "No" << endl;}}