제출 #1370810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1370810		domi	결혼 문제 (IZhO14_marriage)	C++20	98 / 100	286 ms	8544 KiB

marriage

#include <bits/stdc++.h>

// #define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 3e4;
const int MMAX = 2e3;

using namespace std;

mt19937_64 rng(time(NULL));

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

unordered_set<int, custom_hash> G[NMAX + 5];
vector<int> T[NMAX + 5];
vector<pair<int, int>> edges;
int viz[NMAX + 5], mate[NMAX + 5], n, m, k;

bool try_match(int u) {
    if (viz[u]) return false;
    viz[u] = true;
    for (auto &v : G[u]) {
        if (mate[v] == -1 || try_match(mate[v])) {
            mate[v] = u;
            return true;
        }
    }

    return false;
}

bool augment(int u) {
    fill(viz + 1, viz + n + 1, 0LL);
    return try_match(u);
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> k;

    for (int i = 0, girl, boy; i < k; ++i) {
        cin >> boy >> girl;
        edges.push_back({boy, girl});
    }

    if (n < m) {
        swap(n, m);
        for (auto &[boy, girl] : edges)
            swap(boy, girl);
    }

    for (auto &[boy, girl] : edges)
        T[boy].push_back(girl);

    for (int v = 1; v <= n; ++v)
        mate[v] = -1;

    queue<int> to_match;
    for (int u = 1; u <= m; ++u)
        to_match.push(u);

    int r = 0, ans = 0;
    for (int l = 1; l <= n; ++l) {
        while (!to_match.empty()) {
            while (!to_match.empty() && augment(to_match.front()))
                to_match.pop();

            if (to_match.empty()) break;

            if (r == n)
                goto afis;

            ++r;
            for (auto &girl : T[r])
                G[girl].insert(r);
        }

        ans += (n - r + 1);
        for (auto &girl : T[l])
            G[girl].erase(l);

        if (mate[l] != -1) {
            to_match.push(mate[l]);
            mate[l] = -1;
        }
    }

    afis:
    cout << ans << '\n';
    return 0;
}

• 서브태스크 1: 98 / 100