Submission #1219316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219316		trufanov.p	결혼 문제 (IZhO14_marriage)	C++20	96 / 100	1595 ms	3180 KiB

marriage

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <queue>
#include <unordered_set>
#include <deque>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long ll;

int n, m, k;
vector<vector<int>> gr1, gr2;

vector<int> usedl, pairr;
vector<int> usedr, pairl;

bool kuhn_left(int v, int timer) {
    usedl[v] = timer;
    for (int u : gr1[v]) {
        if (pairr[u] == -1 || (usedl[pairr[u]] != timer && kuhn_left(pairr[u], timer))) {
            pairr[u] = v;
            pairl[v] = u;
            return true;
        }
    }
    return false;
}

bool kuhn_right(int v, int timer, int min_allow, int max_allow) {
    usedr[v] = timer;
    for (int u : gr2[v]) {
        if ((u >= min_allow && u <= max_allow) && (pairl[u] == -1 || (usedr[pairl[u]] != timer && kuhn_right(pairl[u], timer, min_allow, max_allow)))) {
            pairl[u] = v;
            pairr[v] = u;
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    if (m > n) {
        cout << 0 << '\n';
        return 0;
    }
    gr1.resize(n);
    gr2.resize(m);
    for (int i = 0; i < k; ++i) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        gr1[u].push_back(v);
        gr2[v].push_back(u);
    }
    usedl.resize(n, -1);
    usedr.resize(m, -1);
    pairl.resize(n, -1);
    pairr.resize(m, -1);
    int timer = 0;
    int cur_match = 0;
    int max_allow = 0;
    while (max_allow < n && cur_match < m) {
        if (kuhn_left(max_allow++, timer++)) {
            cur_match++;
        }
    }
    if (cur_match < m) {
        cout << 0 << '\n';
        return 0;
    }
    ll ans = (n - max_allow + 1);
    for (int i = 1; i < n; ++i) {
        if (pairl[i - 1] != -1) {
            int girl = pairl[i - 1];
            pairr[girl] = -1;
            pairl[i - 1] = -1;
            cur_match--;
            if (kuhn_right(girl, timer++, i, max_allow - 1)) {
                cur_match++;
            } else {
                while (max_allow < n && cur_match < m) {
                    if (kuhn_left(max_allow++, timer++)) {
                        cur_match++;
                    }
                }
            }
        }
        if (cur_match != m) {
            break;
        }
        ans += (n - max_allow + 1);
    }
    cout << ans << '\n';
}

• Subtask 1: 96 / 100