結果

問題 No.2346 Replace!!
ユーザー CyanmondCyanmond
提出日時 2023-06-09 23:26:14
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,981 bytes
コンパイル時間 2,311 ms
コンパイル使用メモリ 215,588 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-10 14:34:21
合計ジャッジ時間 4,480 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 12 ms
5,376 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 4 ms
5,376 KB
testcase_14 AC 3 ms
5,376 KB
testcase_15 AC 4 ms
5,376 KB
testcase_16 AC 3 ms
5,376 KB
testcase_17 AC 4 ms
5,376 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 1 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 6 ms
5,376 KB
testcase_32 AC 4 ms
5,376 KB
testcase_33 AC 5 ms
5,376 KB
testcase_34 AC 4 ms
5,376 KB
testcase_35 AC 5 ms
5,376 KB
testcase_36 AC 4 ms
5,376 KB
testcase_37 AC 4 ms
5,376 KB
testcase_38 AC 4 ms
5,376 KB
testcase_39 AC 4 ms
5,376 KB
testcase_40 AC 4 ms
5,376 KB
testcase_41 AC 5 ms
5,376 KB
testcase_42 WA -
testcase_43 AC 4 ms
5,376 KB
testcase_44 AC 6 ms
5,376 KB
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 AC 17 ms
5,376 KB
testcase_53 WA -
testcase_54 AC 6 ms
5,376 KB
testcase_55 AC 4 ms
5,376 KB
testcase_56 AC 9 ms
5,376 KB
testcase_57 AC 37 ms
5,376 KB
testcase_58 AC 4 ms
5,376 KB
testcase_59 AC 4 ms
5,376 KB
testcase_60 AC 5 ms
5,376 KB
testcase_61 AC 36 ms
5,376 KB
testcase_62 AC 5 ms
5,376 KB
testcase_63 AC 5 ms
5,376 KB
testcase_64 AC 35 ms
5,376 KB
testcase_65 AC 32 ms
5,376 KB
testcase_66 WA -
testcase_67 AC 36 ms
5,376 KB
testcase_68 AC 36 ms
5,376 KB
testcase_69 WA -
testcase_70 WA -
testcase_71 WA -
testcase_72 WA -
testcase_73 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include "atcoder/dsu"

using i64 = long long;

std::mt19937 mt;
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;
    }

    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;
    const auto groups = uft.groups();
    for (const auto &vs : 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[cycle[i]] = i;
        }

        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]) {
                destination[f] = x;
                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;
            }
        }

        if (not isOk) break;
        bool h = false;
        for (int i = 0; i < u; ++i) {
            const int t = destination[cycle[i]];
            int x = cycle[i];
            bool hu = true;
            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) {
                    hu = false;
                    break;
                }
                x = A[x];
            }
            if (hu) {
                h = true;
                break;
            }
        }
        if (not h) isOk = false;
        if (not isOk) break;
    }
    std::cout << (isOk ? "Yes" : "No") << std::endl;
}

int main() {
    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }
}
0