結果
問題 | No.2316 Freight Train |
ユーザー | gyozasukisuki |
提出日時 | 2023-05-26 21:39:49 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 451 ms / 2,000 ms |
コード長 | 1,752 bytes |
コンパイル時間 | 2,079 ms |
コンパイル使用メモリ | 200,368 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-08-26 10:50:00 |
合計ジャッジ時間 | 14,445 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 438 ms
4,380 KB |
testcase_04 | AC | 233 ms
4,380 KB |
testcase_05 | AC | 166 ms
4,376 KB |
testcase_06 | AC | 56 ms
4,380 KB |
testcase_07 | AC | 379 ms
4,380 KB |
testcase_08 | AC | 245 ms
4,380 KB |
testcase_09 | AC | 325 ms
4,380 KB |
testcase_10 | AC | 351 ms
4,380 KB |
testcase_11 | AC | 303 ms
4,376 KB |
testcase_12 | AC | 371 ms
4,376 KB |
testcase_13 | AC | 443 ms
4,380 KB |
testcase_14 | AC | 441 ms
4,376 KB |
testcase_15 | AC | 447 ms
4,380 KB |
testcase_16 | AC | 451 ms
4,380 KB |
testcase_17 | AC | 438 ms
4,380 KB |
testcase_18 | AC | 445 ms
4,376 KB |
testcase_19 | AC | 449 ms
4,380 KB |
testcase_20 | AC | 448 ms
4,380 KB |
testcase_21 | AC | 437 ms
4,376 KB |
testcase_22 | AC | 443 ms
4,380 KB |
testcase_23 | AC | 405 ms
4,380 KB |
testcase_24 | AC | 436 ms
4,380 KB |
testcase_25 | AC | 416 ms
4,376 KB |
testcase_26 | AC | 412 ms
4,380 KB |
testcase_27 | AC | 314 ms
4,380 KB |
testcase_28 | AC | 2 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> //#include <atcoder/all> //using namespace atcoder; using namespace std; const int INF = 1e9; using ll = long long; using inv = vector<int>; using stv = vector<string>; using pint = pair<int,int>; #define FOR(i,l,r) for(int i=(l); i<(r); i++) #define rep(i,r) for(int i=0; i<(r); i++) #define repl(i,r) for(long long i=0; i<(r); i++) #define FORl(i,l,r) for(long long i=(l); i<(r); i++) #define INFL ((1LL<<62)-(1LL<<31)) #define pb(x) push_back(x) #define CIN(x) cin >> x const ll MOD = 1e9+7; struct UnionFind { vector<int> par; UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化 for(int i = 0; i < N; i++) par[i] = i; } int root(int x) { // データxが属する木の根を再帰で得る:root(x) = {xの木の根} if (par[x] == x) return x; return par[x] = root(par[x]); } void unite(int x, int y) { // xとyの木を併合 int rx = root(x); //xの根をrx int ry = root(y); //yの根をry if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時:xの根rxをyの根ryにつける } bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す int rx = root(x); int ry = root(y); return rx == ry; } }; int main(){ int N,Q; cin >> N >>Q; UnionFind d(N); rep(i,N){ int p; cin >> p; if(p == -1) continue; p--; d.unite(i,p); } rep(i,Q){ int a,b; cin >> a >> b; a--,b--; cout << (d.same(a,b) ? "Yes" : "No") << endl; } }