結果

問題 No.2346 Replace!!
ユーザー CyanmondCyanmond
提出日時 2023-06-09 22:54:02
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,960 bytes
コンパイル時間 2,378 ms
コンパイル使用メモリ 210,332 KB
最終ジャッジ日時 2025-02-14 00:28:46
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 16 WA * 19 TLE * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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();
    }
}
0