結果

問題 No.2346 Replace!!
ユーザー CyanmondCyanmond
提出日時 2023-06-09 23:35:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,749 bytes
コンパイル時間 3,545 ms
コンパイル使用メモリ 212,840 KB
実行使用メモリ 5,200 KB
最終ジャッジ日時 2023-08-30 14:44:12
合計ジャッジ時間 6,725 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 12 ms
4,380 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 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
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 2 ms
4,380 KB
testcase_29 AC 3 ms
4,380 KB
testcase_30 AC 2 ms
4,380 KB
testcase_31 AC 6 ms
4,384 KB
testcase_32 AC 4 ms
4,376 KB
testcase_33 AC 5 ms
4,380 KB
testcase_34 WA -
testcase_35 AC 4 ms
4,384 KB
testcase_36 AC 4 ms
4,380 KB
testcase_37 AC 5 ms
4,384 KB
testcase_38 AC 5 ms
4,380 KB
testcase_39 AC 5 ms
4,380 KB
testcase_40 AC 4 ms
4,384 KB
testcase_41 AC 5 ms
4,380 KB
testcase_42 AC 4 ms
4,380 KB
testcase_43 AC 5 ms
4,380 KB
testcase_44 AC 6 ms
4,380 KB
testcase_45 AC 4 ms
4,380 KB
testcase_46 AC 5 ms
4,380 KB
testcase_47 AC 4 ms
4,376 KB
testcase_48 AC 4 ms
4,380 KB
testcase_49 AC 5 ms
4,380 KB
testcase_50 AC 4 ms
4,384 KB
testcase_51 AC 51 ms
4,384 KB
testcase_52 AC 33 ms
4,380 KB
testcase_53 AC 21 ms
4,380 KB
testcase_54 AC 6 ms
4,376 KB
testcase_55 AC 5 ms
4,380 KB
testcase_56 AC 10 ms
4,380 KB
testcase_57 AC 78 ms
4,376 KB
testcase_58 AC 4 ms
4,376 KB
testcase_59 AC 5 ms
4,380 KB
testcase_60 AC 4 ms
4,376 KB
testcase_61 AC 79 ms
4,376 KB
testcase_62 AC 4 ms
4,376 KB
testcase_63 AC 6 ms
4,384 KB
testcase_64 AC 79 ms
4,376 KB
testcase_65 WA -
testcase_66 AC 16 ms
4,384 KB
testcase_67 AC 79 ms
4,380 KB
testcase_68 AC 79 ms
4,380 KB
testcase_69 AC 52 ms
4,380 KB
testcase_70 AC 78 ms
4,376 KB
testcase_71 AC 78 ms
4,380 KB
testcase_72 AC 79 ms
4,380 KB
testcase_73 AC 32 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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;
        std::vector<int> dc(u);
        for (int i = 0; i < u; ++i) {
            const int t = destination[cycle[i]];
            int x = cycle[i];
            bool hu = true;
            while (x != t) {
                ++dc[cycleId[x]];
                x = A[x];
            }
        }
        if (*std::min_element(dc.begin(), dc.end()) != 0) isOk = false; 
        if (not isOk) break;
    }
    std::cout << (isOk ? "Yes" : "No") << std::endl;
}

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