Submission #331918

#	Time	Username	Problem	Language	Result	Execution time	Memory
331918		vitkishloh228	Marriage questions (IZhO14_marriage)	C++14	100 / 100	952 ms	2156 KiB

marriage

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> mt;
vector<vector<int>> g;
vector<int> mt1;
int L = 0, R = 0;
vector<bool> used;
bool dfs(int v) {
    if (used[v]) return false;
    used[v] = true;
    for (auto u : g[v]) {
        if (L <= u && u <= R) {
            if (mt[u] == -1 || dfs(mt[u])) {
                mt[u] = v;
                mt1[v] = u;
                return true;
            }
        }
    }
    return false;
}
int main() {
    int m, n, k;
    cin >> m >> n >> k;
    g.resize(n);
    while (k--) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[v].push_back(u);
    }
    used.resize(n);
    mt = vector<int>(m, -1);
    mt1 = vector<int>(n, -1);
    queue<int> q;
    for (int i = 0; i < n; ++i) {
        q.push(i);
    }
    long long ans = 0;
    for (L = 0, R = -1; max(R, L) < m;) {
        while (max(R, L) < m && !q.empty()) {
            while (!q.empty()) {
                int v = q.front();
                used = vector<bool>(n, false);
                if (dfs(v)) {
                    q.pop();
                }
                else break;
            }
            if (q.empty()) break;
            R++;
        }

        ans += m - R;
        int v0 = mt[L];
        if (v0 != -1) {
            mt[L] = -1;
            q.push(v0);
        }
        L++;
    }
    cout << ans;
}

• Subtask 1: 100 / 100