結果
| 問題 | No.2346 Replace!! |
| ユーザー |
 Cyanmond
|
| 提出日時 | 2023-06-09 22:54:02 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,960 bytes |
| コンパイル時間 | 2,610 ms |
| コンパイル使用メモリ | 217,224 KB |
| 実行使用メモリ | 13,756 KB |
| 最終ジャッジ日時 | 2024-06-10 14:04:48 |
| 合計ジャッジ時間 | 6,279 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
13,756 KB |
| testcase_01 | AC | 33 ms
6,944 KB |
| testcase_02 | TLE | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
ソースコード
#include <bits/stdc++.h>
#include "atcoder/dsu"
using i64 = long long;
void solve() {
int N;
std::cin >> N;
std::vector<int> A(N), B(N);
for (auto &e : A) {
std::cin >> e;
--e;
}
for (auto &e : B) {
std::cin >> e;
--e;
}
std::vector<std::vector<int>> rgraph(N);
for (int i = 0; i < N; ++i) rgraph[A[i]].push_back(i);
atcoder::dsu uft(N);
for (int i = 0; i < N; ++i) uft.merge(i, A[i]);
std::vector<bool> isUsed(N);
std::vector<int> cycleId(N), destination(N), sMi(N);
bool isOk = true;
for (const auto &vs : uft.groups()) {
std::vector<int> cycle;
{
int v = vs.front();
while (true) {
if (isUsed[v]) {
const auto itr = std::find(cycle.begin(), cycle.end(), v);
cycle.erase(cycle.begin(), itr);
break;
} else {
cycle.push_back(v);
isUsed[v] = true;
v = A[v];
}
}
}
const int u = (int)cycle.size();
for (int i = 0; i < u; ++i) {
cycleId[cycle[i]] = i;
sMi[i] = i;
}
for (const auto e : cycle) std::cerr << e << ' ';
std::cerr << std::endl;
auto add = [&](int i, int f) {
const int a = cycleId[i], b = cycleId[f];
const int c = sMi[i];
int sb = a >= b ? (a - b) : (a + N - b);
int sc = a >= c ? (a - c) : (a + N - c);
if (sb < sc) sMi[i] = b;
};
for (const auto f : vs) {
int x = f;
int cnt = 0;
if (A[x] == B[f]) {
continue;
}
while (A[A[x]] != B[f]) {
x = A[x];
++cnt;
if (cnt > 2 * N) {
isOk = false;
break;
}
}
if (not isOk) break;
if (std::find(cycle.begin(), cycle.end(), f) != cycle.end()) {
// in cycle
destination[f] = A[x];
add(x, f);
} else {
continue;
}
}
bool h = false;
for (int i = 0; i < u; ++i) {
const int t = destination[cycle[i]];
int x = cycle[i];
while (x != t) {
const int c = sMi[x], b = i;
const int sb = x >= b ? (x - b) : (x + N - b), sc = x >= c ? (x - c) : (x + N - c);
if (sb < sc) {
h = true;
break;
}
x = A[x];
}
if (h) break;
}
if (h) isOk = false;
if (not isOk) break;
}
std::cout << (isOk ? "Yes" : "No") << std::endl;
}
int main() {
int T;
std::cin >> T;
while (T--) {
solve();
}
}