結果
問題 | No.2316 Freight Train |
ユーザー |
|
提出日時 | 2023-06-29 19:18:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 805 bytes |
コンパイル時間 | 1,946 ms |
コンパイル使用メモリ | 193,536 KB |
最終ジャッジ日時 | 2025-02-15 03:08:58 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll=long long;using pii=pair<int,int>;#define all(a) a.begin(),a.end()#define pb push_back#define sz(a) ((int)a.size())const int N=200005;int par[N],siz[N];void init_dsu(int n){for(int i=0; i<n; ++i) par[i]=i,siz[i]=1;}int Find(int x){return x==par[x]?x:par[x]=Find(par[x]);}bool Union(int x, int y){x=Find(x),y=Find(y);if(x==y) return 0;if(siz[x]<siz[y]) swap(x,y);siz[x]+=siz[y],par[y]=x;return 1;}int n,q;signed main(){ios_base::sync_with_stdio(0),cin.tie(0);cin >> n >> q;init_dsu(n);for(int i=0; i<n; ++i){int x; cin >> x;if(x!=-1) Union(i,x-1);}while(q--){int x,y; cin >> x >> y; x--,y--;cout << (Find(x)==Find(y)?"Yes":"No") << "\n";}}