結果
問題 | No.2316 Freight Train |
ユーザー |
![]() |
提出日時 | 2023-06-23 17:47:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 1,558 bytes |
コンパイル時間 | 485 ms |
コンパイル使用メモリ | 53,840 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-30 21:43:43 |
合計ジャッジ時間 | 5,096 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
/* -*- coding: utf-8 -*-** 2316.cc: No.2316 Freight Train - yukicoder*/#include<cstdio>#include<vector>#include<algorithm>using namespace std;/* constant */const int MAX_N = 200000;/* typedef */struct UFT {vector<int> links, ranks, sizes;UFT() {}void init(int n) {links.resize(n);for (int i = 0; i < n; i++) links[i] = i;ranks.assign(n, 1);sizes.assign(n, 1);}int root(int i) {int i0 = i;while (links[i0] != i0) i0 = links[i0];return (links[i] = i0);}int rank(int i) { return ranks[root(i)]; }int size(int i) { return sizes[root(i)]; }bool same(int i, int j) { return root(i) == root(j); }int merge(int i0, int i1) {int r0 = root(i0), r1 = root(i1), mr;if (r0 == r1) return r0;if (ranks[r0] == ranks[r1]) {links[r1] = r0;sizes[r0] += sizes[r1];ranks[r0]++;mr = r0;}else if (ranks[r0] > ranks[r1]) {links[r1] = r0;sizes[r0] += sizes[r1];mr = r0;}else {links[r0] = r1;sizes[r1] += sizes[r0];mr = r1;}return mr;}};/* global variables */int ps[MAX_N];UFT uft;/* subroutines *//* main */int main() {int n, qn;scanf("%d%d", &n, &qn);for (int i = 0; i < n; i++) scanf("%d", ps + i), ps[i]--;uft.init(n);for (int i = 0; i < n; i++)if (ps[i] >= 0)uft.merge(i, ps[i]);while (qn--) {int a, b;scanf("%d%d", &a, &b);a--, b--;if (uft.same(a, b)) puts("Yes");else puts("No");}return 0;}