Submission #92775

#	Time	Username	Problem	Language	Result	Execution time	Memory
92775		SamAnd	결혼 문제 (IZhO14_marriage)	C++17	48 / 100	1580 ms	33784 KiB

marriage

#pragma comment(linker,"/STACK:200000000")
#define _CRT_SECURE_NO_WARNINGS
#define mp make_pair
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <cstring>
void fp();
void sp();
using namespace std;
const int N = 2003;
struct ban
{
	int x, d;
};

int n1, n2, m;
int n;
int ans;
vector<int> a[N];
int b[N][N];
int p[N];
bool c[N];
bool dfs(int x, int pp)
{
	c[x] = true;
	p[x] = pp;
	if (x == n)
		return true;
	for (int i = 0; i <= n; ++i)
	{
		if (!c[i] && b[x][i])
		{
			if (dfs(i, x))
				return true;
		}
	}
	return false;
}
bool stg(int l, int r)
{
	for (int i = 0; i <= n; ++i)
	{
		for (int j = 0; j <= n; ++j)
		{
			b[i][j] = 0;
		}
	}
	for (int i = l; i <= r; ++i)
	{
		b[0][i] = 1;
		for (int j = 0; j<a[i].size(); ++j)
		{
			b[i][a[i][j]] = 1;
		}
	}
	for (int i = n1 + 1; i<n; ++i)
	{
		b[i][n] = 1;
	}
	for (int i = 0; i <= n; ++i)
		c[i] = false;
	while (dfs(0, -1))
	{
		int minu = N;
		for (int x = n; x != 0; x = p[x])
		{
			minu = min(minu, b[p[x]][x]);
		}
		for (int x = n; x != 0; x = p[x])
		{
			b[p[x]][x] -= minu;
			b[x][p[x]] += minu;
		}
		for (int i = 0; i <= n; ++i)
			c[i] = false;
	}
	int res = 0;
	for (int i = 0; i <= n; ++i)
	{
		res += b[n][i];
	}
	return res == (n2);
}
int main()
{
	ios_base::sync_with_stdio(false);
	//fp();
	cin >> n1 >> n2 >> m;
	n = n1 + n2 + 1;
	for (int i = 0; i<m; ++i)
	{
		int x, y;
		cin >> x >> y;
		a[x].push_back(y + n1);
	}
	if (n2 == 1)
	{
		for (int l = 1; l <= n1; ++l)
		{
			for (int r = l; r <= n1; ++r)
			{
				if ((r - l + 1)<n2)
					continue;
				if (stg(l, r))
				{
					++ans;
				}
			}
		}
	}
	else
	{
		for (int l = 1; l <= n1; ++l)
		{
			for (int r = l + 1; r <= n1; ++r)
			{
				if ((r - l + 1)<n2)
					continue;
				if (stg(l, r))
				{
					++ans;
				}
			}
		}
	}
	cout << ans << endl;
	sp();
	return 0;
}

void fp()
{
#ifndef OLYMP
	freopen("marriage.in", "r", stdin);
	freopen("marriage.out", "w", stdout);
#endif
}
void sp()
{
#ifdef OLYMP
	system("pause");
#endif
}

Compilation message (stderr)

marriage.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker,"/STACK:200000000")
 
marriage.cpp: In function 'bool stg(int, int)':
marriage.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j<a[i].size(); ++j)
                   ~^~~~~~~~~~~~
marriage.cpp: In function 'void fp()':
marriage.cpp:142:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("marriage.in", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:143:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("marriage.out", "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 48 / 100