結果
問題 | No.1983 [Cherry 4th Tune C] 南の島のマーメイド |
ユーザー | SSRS |
提出日時 | 2022-06-17 21:40:17 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 815 ms / 4,000 ms |
コード長 | 2,187 bytes |
コンパイル時間 | 2,332 ms |
コンパイル使用メモリ | 174,168 KB |
実行使用メモリ | 82,192 KB |
最終ジャッジ日時 | 2023-07-30 11:57:37 |
合計ジャッジ時間 | 23,390 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 14 ms
4,376 KB |
testcase_09 | AC | 22 ms
5,212 KB |
testcase_10 | AC | 21 ms
5,660 KB |
testcase_11 | AC | 26 ms
5,600 KB |
testcase_12 | AC | 17 ms
4,376 KB |
testcase_13 | AC | 490 ms
32,072 KB |
testcase_14 | AC | 527 ms
36,204 KB |
testcase_15 | AC | 548 ms
48,156 KB |
testcase_16 | AC | 296 ms
43,204 KB |
testcase_17 | AC | 512 ms
37,568 KB |
testcase_18 | AC | 423 ms
48,900 KB |
testcase_19 | AC | 531 ms
57,048 KB |
testcase_20 | AC | 449 ms
45,148 KB |
testcase_21 | AC | 465 ms
43,276 KB |
testcase_22 | AC | 534 ms
46,028 KB |
testcase_23 | AC | 759 ms
60,460 KB |
testcase_24 | AC | 809 ms
60,508 KB |
testcase_25 | AC | 805 ms
60,756 KB |
testcase_26 | AC | 800 ms
60,344 KB |
testcase_27 | AC | 777 ms
60,388 KB |
testcase_28 | AC | 771 ms
60,496 KB |
testcase_29 | AC | 785 ms
60,560 KB |
testcase_30 | AC | 815 ms
60,296 KB |
testcase_31 | AC | 764 ms
60,452 KB |
testcase_32 | AC | 805 ms
60,368 KB |
testcase_33 | AC | 2 ms
4,380 KB |
testcase_34 | AC | 545 ms
45,276 KB |
testcase_35 | AC | 798 ms
82,192 KB |
testcase_36 | AC | 632 ms
55,828 KB |
testcase_37 | AC | 1 ms
4,380 KB |
testcase_38 | AC | 318 ms
4,376 KB |
testcase_39 | AC | 802 ms
82,124 KB |
testcase_40 | AC | 661 ms
52,196 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; const int LOG = 18; void dfs(vector<vector<int>> &E, vector<int> &d, vector<int> &p, vector<vector<int>> &c, vector<int> &in, int v){ in.push_back(v); for (int w : E[v]){ if (d[w] == -1){ d[w] = d[v] + 1; p[w] = v; c[v].push_back(w); dfs(E, d, p, c, in, w); } } } int main(){ int N, M, Q; cin >> N >> M >> Q; vector<vector<int>> E(N); for (int i = 0; i < M; i++){ int u, v; cin >> u >> v; u--; v--; E[u].push_back(v); E[v].push_back(u); } vector<int> p(N, -1); vector<vector<int>> c(N); vector<int> d(N, -1); vector<int> imos(N, 0); vector<int> in; for (int i = 0; i < N; i++){ if (d[i] == -1){ d[i] = 0; if (i > 0){ p[i] = 0; c[0].push_back(i); d[i] = 1; imos[i]++; imos[0]--; } dfs(E, d, p, c, in, i); } } for (int i = 0; i < N; i++){ for (int j : E[i]){ if (d[j] < d[i] - 1){ imos[i]++; imos[j]--; } } } reverse(in.begin(), in.end()); for (int v : in){ if (v != 0){ imos[p[v]] += imos[v]; } } vector<vector<int>> pp(LOG, vector<int>(N, -1)); pp[0] = p; vector<vector<int>> sum(LOG, vector<int>(N, 0)); sum[0] = imos; for (int i = 0; i < LOG - 1; i++){ for (int j = 0; j < N; j++){ if (pp[i][j] != -1){ pp[i + 1][j] = pp[i][pp[i][j]]; if (pp[i + 1][j] != -1){ sum[i + 1][j] = sum[i][j] + sum[i][pp[i][j]]; } } } } for (int i = 0; i < Q; i++){ int x, y; cin >> x >> y; x--; y--; if (d[x] > d[y]){ swap(x, y); } int s = 0; for (int j = 0; j < LOG; j++){ if (((d[y] - d[x]) >> j & 1) == 1){ s += sum[j][y]; y = pp[j][y]; } } if (x != y){ for (int j = LOG - 1; j >= 0; j--){ if (pp[j][x] != pp[j][y]){ s += sum[j][x]; s += sum[j][y]; x = pp[j][x]; y = pp[j][y]; } } s += sum[0][x]; s += sum[0][y]; } if (s == 0){ cout << "Yes" << endl; } else { cout << "No" << endl; } } }