結果
問題 | No.2316 Freight Train |
ユーザー |
![]() |
提出日時 | 2023-05-26 21:26:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 499 ms / 2,000 ms |
コード長 | 846 bytes |
コンパイル時間 | 4,306 ms |
コンパイル使用メモリ | 251,576 KB |
最終ジャッジ日時 | 2025-02-13 05:45:03 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;typedef modint998244353 mint;typedef long long ll;struct UnionFind{int n;vector<int> par;explicit UnionFind(int v): n(v), par(v,-1) {}void merge(int a, int b){int x = find(a);int y = find(b);if (x == y) return;if (-par[x] < -par[y]) swap(x, y);par[x] += par[y];par[y] = x;return;}int find(int x){if (par[x] < 0) return x;return par[x] = find(par[x]);}};int main(){int n, q; cin >> n >> q;UnionFind uf(n);vector<int> p(n);for (int i=0; i<n; i++){cin >> p[i];}for (int i=0; i<n; i++){if (p[i] != -1){uf.merge(p[i]-1, i);}}for (int i=0; i<q; i++){int a, b; cin >> a >> b;a--; b--;if (uf.find(a) == uf.find(b)){cout << "Yes\n";}else{cout << "No\n";}}}