Submission #1202241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202241		LucaIlie	Marriage questions (IZhO14_marriage)	C++20	66 / 100	1033 ms	1216 KiB

marriage

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e4;
const int MAX_M = 2000;
vector<int> adj[MAX_M + 1];
bool vis[MAX_N + 1];
int pairB[MAX_N + 1];
set<int> unpaired;
int L, R;

bool pairup(int u) {
    if (u == 0)
        return true;

    if (vis[u])
        return false;

    vis[u] = true;
    for (int v: adj[u]) {
        if (v < L || v > R)
            continue;
        if (pairup(pairB[v])) {
            pairB[v] = u;
            return true;
        }
    }

    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;

    cin >> n >> m >> k;
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> b >> a;
        adj[a].push_back(b);
    }
    
    for (int i = 1; i <= m; i++)
        unpaired.insert(i);

    int l = 1;
    long long ans = 0;
    for (int r = 1; r <= n; r++) {
        L = l;
        R = r;
        vector<int> ers;
        for (int i = 1; i <= m; i++)
            vis[i] = false;
        for (int i: unpaired) {
            if (pairup(i))
                ers.push_back(i);
        }
        for (int i: ers)
            unpaired.erase(i);

        if (unpaired.empty()) {
            while (l <= r && unpaired.empty()) {
                int i = pairB[l];
                pairB[l] = 0;
                l++;
                L = l, R = r;
                unpaired.insert(i);
                vis[i] = false;
                if (pairup(i))
                    unpaired.erase(i);
            }
            l--;
            ans += l;
       //     printf("%d %d\n", l, r);
        }
        
    }

    cout << ans << "\n";
}

• Subtask 1: 66 / 100