結果
問題 | No.2316 Freight Train |
ユーザー |
👑 |
提出日時 | 2023-05-30 10:20:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 521 ms / 2,000 ms |
コード長 | 1,020 bytes |
コンパイル時間 | 695 ms |
コンパイル使用メモリ | 75,408 KB |
最終ジャッジ日時 | 2025-02-13 16:29:47 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <iostream>#include <vector>using namespace std;struct UnionFind {int n;vector<int> par;vector<int> size_;UnionFind(int n_) : n(n_), par((size_t)n_), size_((size_t)n_,1){for(int i = 0; n > i; i++)par[i] = i;}int root(int x){if(par[x] == x)return x;return par[x] = root(par[x]);}void unite(int a,int b){int ra = root(a);int rb = root(b);if(ra==rb)return;if(size(ra) > size(rb)) swap(ra,rb);par[ra] = rb;size_[rb] += size_[ra];}bool same(int a, int b){return root(a) == root(b);}int size(int a){return size_[root(a)];}void debug(){for(int i = 0; n > i; i++){cout << size_[root(i)] << " ";}cout << endl;return;}};int main(){int n,q;cin>>n>>q;UnionFind A(n);for(int i = 0; n > i; i++){int x;cin>>x;if(x != -1){A.unite(i,x-1);}}for(int i = 0; q > i; i++){int a,b;cin>>a>>b;cout << (A.same(a-1, b-1) ? "Yes" : "No") << endl;}}