ABC 395

Table of Contents

D - Pigeon Swap

https://atcoder.jp/contests/abc395/tasks/abc395_d

想定と違う方法で解けたがすごく複雑なことをしてしまった。

提出コードでは鳩 $i$ が配置されたときの index とその時の巣の番号と、箱を swap したときの履歴を管理して解いた。 種別 1 のクエリで鳩を移動させたあとに箱の swap があった場合は、swap の履歴をたどって最終的な巣の番号を求めた。

void solve() {
    int N, Q;
    cin >> N >> Q;

    // 配置されたときの index, その時の巣の番号
    vector<pair<int, int>> hato(N);
    // 入れ替えがあったときの index, 移動先の巣の番号
    vector<vector<pair<int, int>>> hako(N);
    rep(i, N) {
        hato[i] = {-1, i};
        hako[i].push_back({-1, i});
    }

    map<pair<int, int>, pair<int, int>> memo;

    rep(i, Q) {
        int t;
        cin >> t;
        if (t == 1) {
            int a, b;
            cin >> a >> b;
            a--, b--;

            hato[a] = {i, b};
        } else if (t == 2) {
            int a, b;
            cin >> a >> b;
            a--, b--;

            hako[a].push_back({i, b});
            hako[b].push_back({i, a});
        } else {
            int a;
            cin >> a;
            a--;

            auto [id, num] = hato[a];
            vector<pair<int, int>> olds;
            while (true) {
                auto it = upper_bound(all(hako[num]), make_pair(id, INF));
                if (it == hako[num].end())
                    break;
                olds.push_back(*it);
                if (memo.count(*it)) {
                    auto x = memo[*it];
                    id = x.first;
                    num = x.second;
                } else {
                    id = it->first;
                    num = it->second;
                }
            }
            if (olds.size())
                olds.pop_back();
            // 経路圧縮
            for (auto [a, b] : olds) {
                memo[{a, b}] = {id, num};
            }
            hato[a] = {id, num};
            cout << num + 1 << endl;
        }
    }
}

解説放送を見たあとの復習

巣の中に袋が入っており、鳩をその袋に入れるという考え方で解く。

void solve() {
    int n, q;
    cin >> n >> q;

    vint p2b(n), b2h(n), h2b(n);
    iota(all(p2b), 0);
    iota(all(b2h), 0);
    iota(all(h2b), 0);

    rep(i, q) {
        int t;
        cin >> t;
        if (t == 1) {
            int a, b;
            cin >> a >> b;
            a--, b--;
            p2b[a] = h2b[b];
        } else if (t == 2) {
            int a, b;
            cin >> a >> b;
            a--, b--;

            // part 1 ~ 3 はどれでも正解
            // part 1
            swap(h2b[a], h2b[b]);
            swap(b2h[h2b[a]], b2h[h2b[b]]);

            // part 2
            // b2h[h2b[a]] = b;
            // b2h[h2b[b]] = a;
            // swap(h2b[a], h2b[b]);

            // part 3
            // swap(h2b[a], h2b[b]);
            // b2h[h2b[a]] = a;
            // b2h[h2b[b]] = b;
        } else {
            int a;
            cin >> a;
            a--;
            cout << b2h[p2b[a]] + 1 << endl;
        }
    }
}

E - Flip Edge

https://atcoder.jp/contests/abc395/tasks/abc395_e

類題: https://atcoder.jp/contests/abc325/tasks/abc325_e

以下のようなグラフ $G(V, E)$ を考える

\begin{align} V &= [1, 2N] \nonumber \\ E &= \{(u,v,1) | (u,v) \in (\text{問題分の辺})\} \nonumber \\ &\cup \{(v+N, u+N, 1) | (u,v) \in (\text{問題分の辺}) \} \nonumber \\ &\cup \{ (i, i+N, X) | i \in [1, N]\} \nonumber \\ &\cup \{ (i+N, i, X) | i \in [1, N]\} \nonumber \end{align} ここで $(u,v,w)$ は頂点 $u$ から頂点 $v$ へのコスト $w$ の辺を表す。

このグラフに対して、頂点 $i$ から頂点 $i+N$ への移動、頂点 $i+N$ から頂点 $i$ への移動がグラフを反転させることに対応している。

このグラフにおいて頂点 1 から出発して、頂点 $N$ または頂点 $2N$ への最短距離のうち短いほうが求める答えである。

struct Edge {
    ll to, cost;
};

void solve() {
    ll N, M, X;
    cin >> N >> M >> X;

    vector<vector<Edge>> graph(2 * N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        graph[u].push_back({v, 1});
        graph[v + N].push_back({u + N, 1});
    }
    rep(i, N) {
        graph[i].push_back({i + N, X});
        graph[i + N].push_back({i, X});
    }

    // cost, pos
    using P = pair<ll, ll>;
    priority_queue<P, vector<P>, greater<P>> pq;
    pq.push({0, 0});

    vll dist(N * 2, INF);
    dist[0] = 0;
    while (pq.size()) {
        auto [cost, pos] = pq.top();
        pq.pop();

        if (dist[pos] < cost)
            continue;

        for (auto [to, cost] : graph[pos]) {
            if (dist[to] <= dist[pos] + cost)
                continue;
            dist[to] = dist[pos] + cost;
            pq.push({dist[to], to});
        }
    }

    cout << min(dist[N - 1], dist[N * 2 - 1]) << endl;
}