Submission #713620

#	Time	Username	Problem	Language	Result	Execution time	Memory
713620		alex_2008	Marriage questions (IZhO14_marriage)	C++14	100 / 100	514 ms	3164 KiB

marriage

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
const int N = 50050;
int n, m, k;
vector <int> g[N];
bool used[N];
int mt[N];
bool kuhn(int v, int L, int R) {
	if (used[v]) return false;
	used[v] = true;
	for (auto it : g[v]) {
		if (it >= L && it <= R) {
			if (mt[it] == -1 || kuhn(mt[it], L, R)) {
				mt[it] = v;
				return true;
			}
		}
	}
	return false;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= k; i++) {
		int a, b;
		cin >> a >> b;
		a += m;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	int l = m, r = n, ind = -1;
	while (l <= r) {
		int mid = (l + r) / 2;
		for (int i = 1; i <= mid; i++) {
			mt[i + m] = -1;
		}
		int cnt = 0;
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= m; j++) {
				used[j] = false;
			}
			if (kuhn(i, 1, mid + m)) ++cnt;
		}
		if (cnt == m) {
			ind = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	if (ind == -1) {
		cout << "0\n";
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		mt[i + m] = -1;
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= m; j++) {
			used[j] = false;
		}
		kuhn(i, 1 + m, ind + m);
	}
	int answ = n - ind + 1;
	for (int i = 1; i <= n; i++) {
		if (mt[i + m] == -1) {
			answ += n - ind + 1;
			continue;
		}
		int girl = mt[i + m];
		while (ind <= n) {
			for (int j = 1; j <= m; j++) {
				used[j] = false;
			}
			if (kuhn(girl, i + 1 + m, ind + m)) break;
			ind++;
		}
		if (ind == n + 1) break;
		answ += n - ind + 1;
	}
	cout << answ << "\n";
	return 0;
}

• Subtask 1: 100 / 100