結果
問題 | No.2316 Freight Train |
ユーザー |
|
提出日時 | 2023-10-25 01:07:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 506 ms / 2,000 ms |
コード長 | 1,054 bytes |
コンパイル時間 | 3,815 ms |
コンパイル使用メモリ | 231,296 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-24 20:12:07 |
合計ジャッジ時間 | 18,499 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using ll = long long;#define rep(i,n) for(ll i=0;i<(n);++i)struct UnionFind{vector<ll> par;vector<ll> size;UnionFind(ll n){par.resize(n+1,-1);size.resize(n+1,1);}ll root(ll x){if(par[x]==-1) return x;return par[x]=root(par[x]);}void unite(ll u,ll v){ll RootU=root(u),RootV=root(v);if(RootU==RootV){return;}if(size[RootU]<size[RootV]){par[RootU]=RootV;size[RootV]+=size[RootU];}else{par[RootV]=RootU;size[RootU]+=size[RootV];}return;}bool same(ll u,ll v){return root(u)==root(v);}};int main(){ll n,q;cin >> n >> q;UnionFind uf(n);rep(i,n){ll p;cin >> p;if(p!=-1) uf.unite(i+1,p);}rep(i,q){ll a,b;cin >> a >> b;cout << (uf.same(a,b)?"Yes":"No") << endl;}}