結果
問題 | No.2316 Freight Train |
ユーザー |
|
提出日時 | 2024-11-17 01:02:50 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 193 ms / 2,000 ms |
コード長 | 1,303 bytes |
コンパイル時間 | 3,121 ms |
コンパイル使用メモリ | 247,220 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-17 01:03:01 |
合計ジャッジ時間 | 10,995 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;#define rep(i, s, e) for (int i = (int)s; i < (int)e; ++i)#define all(a) (a).begin(), (a).end()struct UnionFind {vector<int> par, siz;int v, group;UnionFind(int n) {par = vector<int>(n, -1);siz = vector<int>(n, 1);v = n;group = n;}int root(int x) {if (par[x] == -1) return x;else return par[x] = root(par[x]);}bool same(int x, int y) {return root(x) == root(y);}bool unite(int x, int y) {x = root(x);y = root(y);if (x == y) return false;if (siz[x] < siz[y]) swap(x, y);par[y] = x;siz[x] += siz[y];group--;return true;}int size(int x) {return siz[root(x)];}};int main() {cin.tie(nullptr);int N, Q;cin >> N >> Q;UnionFind uf(N);rep(i, 0, N) {int P;cin >> P;if (P == -1) continue;P--;uf.unite(i, P);}rep(query, 0, Q) {int A, B;cin >> A >> B;A--, B--;if (uf.same(A, B)) cout << "Yes\n";else cout << "No\n";}}