lessons/参考实现/07-二分图/CodeForces-1139E.cpp

#include <functional>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, clubs; cin >> n >> clubs;
    vector<int> potential(n), club(n);
    for (int &x : potential) cin >> x;
    for (int &x : club) cin >> x, --x;
    int days; cin >> days;
    vector<int> removed(days); vector<bool> will_remove(n, false);
    for (int &x : removed) { cin >> x; --x; will_remove[x] = true; }

    constexpr int max_potential = 5000;
    vector<vector<int>> graph(max_potential + 1);
    for (int i = 0; i < n; ++i) if (!will_remove[i]) graph[potential[i]].push_back(club[i]);
    vector<int> match_club(clubs, -1), seen(clubs, 0);
    int token = 0;
    function<bool(int)> augment = [&](int p) {
        for (int c : graph[p]) if (seen[c] != token) {
            seen[c] = token;
            if (match_club[c] == -1 || augment(match_club[c])) {
                match_club[c] = p; return true;
            }
        }
        return false;
    };
    int mex = 0;
    auto advance = [&] {
        while (mex <= clubs) {
            ++token;
            if (!augment(mex)) break;
            ++mex;
        }
    };
    advance();
    vector<int> answer(days);
    for (int day = days - 1; day >= 0; --day) {
        answer[day] = mex;
        int student = removed[day];
        graph[potential[student]].push_back(club[student]);
        advance();
    }
    for (int x : answer) cout << x << '\n';
}