結果

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

ソースコード

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