제출 #1280062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280062		longdeptrai	Swap (BOI16_swap)	C++20	0 / 100	0 ms	332 KiB

swap

#include <bits/stdc++.h>
using namespace std;

/*
 Full program:
  - Read bipartite graph: left 1..n (positions), right 1..n (values).
  - Run Hopcroft-Karp to obtain an initial perfect matching (matchingL/matchingR).
  - For i = 1..n: run BFS on alternating directed graph from left i to find reachable right nodes,
    pick the smallest reachable value among adjL[i] (or keep current matched value if better),
    reconstruct alternation path and flip edges along it, then ban left i and chosen right (so they are fixed).
  - Output ans[1..n].

 Input format:
  n
  k1 v11 v12 ... v1k1
  k2 v21 v22 ... v2k2
  ...
  kn vn1 vn2 ... vnk_n
*/

int n;
vector<vector<int>> adjL;    // adjL[1..n]: list of possible values for left u
vector<int> matchingL;      // matchingL[u] = matched value (0 if none)
vector<int> matchingR;      // matchingR[v] = matched left (0 if none)

// Hopcroft-Karp implementation for left 1..n, right 1..n
struct HopcroftKarp {
    int n;
    vector<vector<int>> *adj;
    vector<int> dist;
    const int INF = 1e9;

    HopcroftKarp(int n_, vector<vector<int>> *adj_) : n(n_), adj(adj_) {
        dist.assign(n+1, 0);
    }

    bool bfs() {
        queue<int> q;
        for (int u = 1; u <= n; ++u) {
            if (matchingL[u] == 0) {
                dist[u] = 0;
                q.push(u);
            } else dist[u] = INF;
        }
        bool reachableFree = false;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : (*adj)[u]) {
                int u2 = matchingR[v];
                if (u2 == 0) { // free on right: found potential augmenting path
                    reachableFree = true;
                } else {
                    if (dist[u2] == INF) {
                        dist[u2] = dist[u] + 1;
                        q.push(u2);
                    }
                }
            }
        }
        return reachableFree;
    }

    bool dfs(int u) {
        for (int v : (*adj)[u]) {
            int u2 = matchingR[v];
            if (u2 == 0 || (dist[u2] == dist[u] + 1 && dfs(u2))) {
                matchingL[u] = v;
                matchingR[v] = u;
                return true;
            }
        }
        dist[u] = INF;
        return false;
    }

    int max_matching() {
        fill(matchingL.begin(), matchingL.end(), 0);
        fill(matchingR.begin(), matchingR.end(), 0);
        int matching = 0;
        while (bfs()) {
            for (int u = 1; u <= n; ++u) {
                if (matchingL[u] == 0) {
                    if (dfs(u)) matching++;
                }
            }
        }
        // Note: matching variable counts augmentations after BFS loops; but to ensure correct
        // count, we can count matched lefts:
        int cnt = 0;
        for (int u = 1; u <= n; ++u) if (matchingL[u] != 0) ++cnt;
        return cnt;
    }
};

// Greedy BFS on alternating directed graph + flip
vector<int> ans;
vector<char> banL, banR;

int bfs_and_flip_choose_min(int start) {
    // visited + parent arrays
    vector<char> visL(n+1, 0), visR(n+1, 0);
    vector<int> parentL(n+1, -1); // parentLeft[u] = right v
    vector<int> parentR(n+1, -1); // parentRight[v] = left u

    queue<int> q;
    visL[start] = 1;
    q.push(start);

    // BFS on alternating graph (we queue left nodes)
    while (!q.empty()) {
        int u = q.front(); q.pop();
        // traverse non-matching edges u -> v (skip edges that are matching edge of u)
        for (int v : adjL[u]) {
            if (banR[v]) continue;
            if (matchingL[u] == v) continue; // matching edge oriented v->u, not u->v
            if (visR[v]) continue;
            visR[v] = 1;
            parentR[v] = u;
            int u2 = matchingR[v];
            if (u2 != 0 && !banL[u2] && !visL[u2]) {
                visL[u2] = 1;
                parentL[u2] = v;
                q.push(u2);
            }
        }
    }

    // pick smallest candidate in adjL[start] that is reachable (or the current matched value)
    int curMatched = matchingL[start];
    int pick = INT_MAX;
    for (int v : adjL[start]) {
        if (banR[v]) continue;
        if (visR[v] || curMatched == v) {
            if (v < pick) pick = v;
        }
    }
    if (pick == INT_MAX) {
        // theoretically shouldn't happen if initial matching is perfect
        // fallback: if current matched value exists and not banned, pick it
        if (curMatched != 0 && !banR[curMatched]) pick = curMatched;
        else return -1;
    }

    // reconstruct and flip along alternation path from start to pick
    int v = pick;
    while (true) {
        int u;
        if (parentR[v] != -1) u = parentR[v];
        else u = start; // if pick was the current matched value and parent not set
        int oldv = matchingL[u];
        matchingL[u] = v;
        matchingR[v] = u;
        if (u == start) break;
        // move to the previous right on path
        v = parentL[u];
        if (v == -1) break; // defensive
    }

    // fix (ban) start and pick
    banL[start] = 1;
    banR[pick] = 1;
    ans[start] = pick;
    return pick;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    adjL.assign(n+1, {});
    for (int i = 1; i <= n; ++i) {
        int k; cin >> k;
        adjL[i].resize(k);
        for (int j = 0; j < k; ++j) cin >> adjL[i][j];
        sort(adjL[i].begin(), adjL[i].end()); // sort so we can pick smallest quickly
    }

    matchingL.assign(n+1, 0);
    matchingR.assign(n+1, 0);

    HopcroftKarp hk(n, &adjL);
    int matched = hk.max_matching();
    // verify perfect matching
    if (matched != n) {
        cout << -1 << '\n';
        return 0;
    }

    // prepare for greedy assignment
    ans.assign(n+1, 0);
    banL.assign(n+1, 0);
    banR.assign(n+1, 0);

    // Greedy for i = 1..n
    for (int i = 1; i <= n; ++i) {
        if (banL[i]) continue; // normally false
        int chosen = bfs_and_flip_choose_min(i);
        if (chosen == -1) {
            cout << -1 << '\n';
            return 0;
        }
        // Optionally clear adjL[i] to speed future iterations (i is banned)
        // adjL[i].clear();
    }

    // output ans[1..n]
    for (int i = 1; i <= n; ++i) {
        if (i > 1) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32