Submission #91332

#	Time	Username	Problem	Language	Result	Execution time	Memory
91332		Just_Solve_The_Problem	Marriage questions (IZhO14_marriage)	C++11	70 / 100	1583 ms	11388 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], gr1[(int)3e4 + 7];
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 <= lr[v].second; i++) {
		int to = gr[v][i];
		if (mt[to] == -1 || kuhn(mt[to])) {
			mt[to] = v;
			prr[v] = to;
			return true;
		}
	}
	return false;
}

bool check(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 && kuhn(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;
	int l, r;
	l = 1;
	r = m;
	for (int i = 1; i <= m; i++) {
		sort(gr[i].begin(), gr[i].end());
		lr[i].second = -1;
		for (int j = 0; j < gr[i].size(); j++) {
			int to = gr[i][j];
			if (l <= to && to <= r) {
				lr[i].second = j;
			}
		}
		lr[i].first = 0;
	}
	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 (check(i, mid)) {
				hi = mid;
			} else {
				lo = mid;
			}
		}
		ans += (n - hi + 1);
	}
	cout << ans << endl;
}

Compilation message (stderr)

marriage.cpp:57:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
marriage.cpp: In function 'int main()':
marriage.cpp:71:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < gr[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~
marriage.cpp:58: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:61: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: 70 / 100