結果
問題 | No.2316 Freight Train |
ユーザー |
![]() |
提出日時 | 2023-05-26 21:43:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 432 ms / 2,000 ms |
コード長 | 2,137 bytes |
コンパイル時間 | 2,161 ms |
コンパイル使用メモリ | 169,508 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-25 05:55:04 |
合計ジャッジ時間 | 12,710 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; // #include <atcoder/all> // using namespace atcoder; using ll = long long; #define reps(i, a, n) for(ll i = (a); i < (ll)(n); ++i) #define rep(i,n) reps(i,0,n) #define all(a) (a).begin(), (a).end(); #define debug(x) cerr << "\033[33m(line:" << __LINE__ << ") " << #x << ": " << x << "\033[m" << endl; //なんかstd::vector<bool>の挙動を修正できるやつ /* alias */ using ull = unsigned long long; using ll = long long; using vi = vector<int>; using vl = vector<long>; using vll = vector<long long>; using vvi = vector<vi>; using vvl = vector<vl>; using vvll = vector<vll>; using vs = vector<string>; using pii = pair<int, int>; //UnionFind木 // @see https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/union-find class UnionFind{ public: UnionFind() = default; // n 要素数 explicit UnionFind(size_t n) : m_parentsOrSize(n, -1){} int root(int i){ if (m_parentsOrSize[i] < 0) return i; // 経路圧縮 return (m_parentsOrSize[i] = root(m_parentsOrSize[i])); } void unite(int a, int b){ a = root(a); b = root(b); if(a != b){ // 小さいほうが子になる if(-m_parentsOrSize[a] < -m_parentsOrSize[b]) swap(a,b); m_parentsOrSize[a] += m_parentsOrSize[b]; m_parentsOrSize[b] = a; } } bool same(int a, int b){ return (root(a) == root(b));} // i が属するグループの要素数を返す int size(int i){return -m_parentsOrSize[root(i)];} private: // m_parentsOrSize[i]は i の親, // ただし root の場合は (-1 * そのグループに属する要素数) vi m_parentsOrSize; // using vi = vector<int> }; int main(){ int n, q; cin >> n >> q; vi a(n); UnionFind uf(n); for(int i = 0; i < n; i++){ cin >> a[i]; if(a[i] != -1) { a[i]--; uf.unite(i,a[i]); } } rep(i, q){ int x, y; cin >> x >> y; x--; y--; if(uf.same(x,y)) cout << "Yes\n"; else cout << "No\n"; } }