Submission #91481

#	Time	Username	Problem	Language	Result	Execution time	Memory
91481		Just_Solve_The_Problem	Marriage questions (IZhO14_marriage)	C++11	100 / 100	382 ms	6024 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];
int used[N], mt[(int)3e4 + 7], prr[N], cnt = 1;
queue < int > q;
int l, r;

bool kuhn(int v) {
	if (used[v] == cnt) return false;
	used[v] = cnt;
	for (int i = 0; i < gr[v].size(); i++) {
		int to = gr[v][i];
		if (to < l) continue;
		if (to > r) break;
		if (mt[to] == -1 || kuhn(mt[to])) {
			mt[to] = v;
			return true;
		}
	}
	return false;
}

bool check() {
	int v;
	while (!q.empty()) {
		v = q.front();
		q.pop();
		cnt++;
		if (!kuhn(v)) {
			q.push(v);
			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());
	}
	memset(mt, -1, sizeof mt);
	for (int i = 1; i <= m; i++) {
		q.push(i);
	}
	r = 1;
	for (int i = 1; i <= n; i++) {
		l = i;
		while (r <= n && !check()) {
			r++;
		}
		ans += (n - r + 1);
		if (mt[i] != -1) {
			q.push(mt[i]);
			mt[i] = -1;
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

marriage.cpp: In function 'bool kuhn(int)':
marriage.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < gr[v].size(); i++) {
                  ~~^~~~~~~~~~~~~~
marriage.cpp: At global scope:
marriage.cpp:46:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
marriage.cpp: In function 'int main()':
marriage.cpp:47: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:50: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: 100 / 100