Submission #340297

#	Time	Username	Problem	Language	Result	Execution time	Memory
340297		_ani	Marriage questions (IZhO14_marriage)	C++17	42 / 100	1586 ms	2796 KiB

marriage

#include <iostream>
#include <vector>
using namespace std;
vector<int> g[2005];
int used[2005];
bool FindHusband(int v, int l, int r)
{
	int mi = 1'000'000, miv = 0;
	for (auto to: g[v])
		if (!used[to] && to / 2 >= l && to / 2 <= r) {
			if (g[to].size() < mi)
			{
				mi = g[to].size();
				miv = to;
			}
		}
	if (miv == 0)return false;
	used[miv] = 1;
	return true;
}
int main()
{
	int n, m, k;
	cin >> n >> m >> k;
	while (k--)
	{
		int a, b;
		cin >> a >> b;
		//a-txa
		g[b * 2].push_back(a * 2 + 1);
		g[a * 2 + 1].push_back(b * 2);
	}
	int ans = 0;
	for (int l = 1; l <= n; l++)
		for (int r = l + m - 1; r <= n; r++)
		{
			bool ok = true;
			for (int i = 1; i <= m; i++)
				if (!FindHusband(2 * i, l, r))
				{
					ok = false;
					break;
				}
			if (ok)ans++;
			for (int k = l; k <= r; k++)
				used[k * 2 + 1] = 0;
		}
	cout << ans;
	return 0;
}

Compilation message (stderr)

marriage.cpp: In function 'bool FindHusband(int, int, int)':
marriage.cpp:11:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   11 |    if (g[to].size() < mi)
      |        ~~~~~~~~~~~~~^~~~

• Subtask 1: 42 / 100