Submission #341237

#	Time	Username	Problem	Language	Result	Execution time	Memory
341237		juggernaut	Marriage questions (IZhO14_marriage)	C++14	100 / 100	472 ms	1260 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) continue;
		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 of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  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]
   46 | 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]
   47 |  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]
   50 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100