Submission #91352

#	Time	Username	Problem	Language	Result	Execution time	Memory
91352		Just_Solve_The_Problem	Marriage questions (IZhO14_marriage)	C++11	86 / 100	1563 ms	1464 KiB

marriage

#include <bits/stdc++.h>
 
using namespace std;
 
#define ok puts("ok");
#define ll long long
 
const int N = (int)2e3 + 7;
 
int n, m, k;
 
vector < int > gr[N];
pair < int, int > lr[N];
int used[N], mt[(int)3e4 + 7], prr[N], cnt = 1;
 
bool kuhn(int v) {
	if (used[v] == cnt) return false;
	used[v] = cnt;
	for (int i = lr[v].first; i < gr[v].size(); i++) {
		int to = gr[v][i];
		if (mt[to] == -1 || kuhn(mt[to])) {
			mt[to] = v;
			prr[v] = to;
			return true;
		}
	}
	return false;
}
 
int check(int l) {
	for (int i = 1; i <= m; i++) {
		while (lr[i].first < (int)gr[i].size() && gr[i][lr[i].first] < l) lr[i].first++;
	}
	memset(mt, -1, sizeof mt);
	memset(prr, -1, sizeof prr);
	int run = 1;
	while (run) {
		run = 0;
		for (int i = 1; i <= m; i++) {
			if (prr[i] == -1 && kuhn(i)) {
				run = 1;
			}
		}
		cnt++;
	}
	int mx = 0;
	for (int i = 1; i <= m; i++) {
		if (prr[i] == -1) {
			return n + 1;
		}
		mx = max(mx, prr[i]);
	}
	return mx;
}

bool kuhn1(int v) {
	if (used[v] == cnt) return false;
	used[v] = cnt;
	for (int i = lr[v].first; i <= lr[v].second; i++) {
		int to = gr[v][i];
		if (mt[to] == -1 || kuhn1(mt[to])) {
			mt[to] = v;
			prr[v] = to;
			return true;
		}
	}
	return false;
}

bool check1(int l, int r) {
	for (int i = 1; i <= m; i++) {
		while (lr[i].first < (int)gr[i].size() && gr[i][lr[i].first] < l) lr[i].first++;
		while (lr[i].first > 0 && gr[i][lr[i].first - 1] >= l) lr[i].first--;
		while (lr[i].second + 1 < (int)gr[i].size() && gr[i][lr[i].second + 1] <= r) lr[i].second++;
		while (lr[i].second >= 0 && gr[i][lr[i].second] > r) lr[i].second--;
	}
	memset(mt, -1, sizeof mt);
	memset(prr, -1, sizeof prr);
	int run = 1;
	while (run) {
		run = 0;
		for (int i = 1; i <= m; i++) {
			if (prr[i] == -1 && kuhn1(i)) {
				run = 1;
			}
		}
		cnt++;
	}
	for (int i = 1; i <= m; i++) {
		if (prr[i] == -1) {
			return 0;
		}
	}
	return 1;
}
 
main() {
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 1; i <= k; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		gr[b].push_back(a);
	}
	ll ans = 0;
	for (int i = 1; i <= m; i++) {
		sort(gr[i].begin(), gr[i].end());
		lr[i].first = 0;
	}
	if (n <= 1000 && m <= 500) {
		for (int i = 1; i <= m; i++) {
			lr[i].second = -1;
			lr[i].first = gr[i].size();
		}
		for (int i = 1; i <= n - m + 1; i++) {
			int lo = i;
			int hi = n + 1;
			while (hi - lo > 1) {
				int mid = (lo + hi) >> 1;
				if (check1(i, mid)) {
					hi = mid;
				} else {
					lo = mid;
				}
			}
			ans += (n - hi + 1);
		}
	} else {
		for (int i = 1; i <= n - m + 1; i++) {
			int res = check(i);
			//cout << i << ' ' << res << endl;
			ans += (n - res + 1);
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

marriage.cpp: In function 'bool kuhn(int)':
marriage.cpp:19:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = lr[v].first; i < gr[v].size(); i++) {
                            ~~^~~~~~~~~~~~~~
marriage.cpp: At global scope:
marriage.cpp:97:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
marriage.cpp: In function 'int main()':
marriage.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 86 / 100