結果

問題 No.3109 Swap members
コンテスト
ユーザー Ryoga.exe
提出日時 2025-04-19 02:56:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 274 ms / 2,000 ms
コード長 1,112 bytes
コンパイル時間 945 ms
コンパイル使用メモリ 85,192 KB
実行使用メモリ 13,672 KB
最終ジャッジ日時 2025-04-19 02:56:25
合計ジャッジ時間 9,208 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 52
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdlib>
#include <iostream>
#include <map>
#include <string>
#include <vector>

struct UnionFind {
    std::vector<int> par;
    UnionFind(const size_t n) : par(n, -1) {}
    int root(const size_t x) { return (par[x] < 0 ? x : par[x] = root(par[x])); }
    bool unite(size_t x, size_t y) {
        x = root(x);
        y = root(y);
        if (x == y) {
            return false;
        }
        if (par[x] > par[y]) {
            std::swap(x, y);
        }
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    inline bool same(const size_t x, const size_t y) { return root(x) == root(y); }
};

int main() {
    int n, k;
    std::cin >> n >> k;
    UnionFind uf(n);
    for (int i = 0; i < n - k; i++) {
        uf.unite(i, i + k);
    }
    std::map<std::string, int> pos;
    for (int i = 0; i < n; i++) {
        std::string tmp;
        std::cin >> tmp;
        pos[tmp] = i;
    }
    bool ng = false;
    for (int i = 0; i < n; i++) {
        std::string tmp;
        std::cin >> tmp;
        ng |= !uf.same(i, pos[tmp]);
    }
    std::cout << (ng ? "No" : "Yes");
}
0