Submission #38013

#	Time	Username	Problem	Language	Result	Execution time	Memory
38013		alenam0161	결혼 문제 (IZhO14_marriage)	C++14	20 / 100	43 ms	4140 KiB

marriage

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cassert>
#include <cstdio>

#define ad push_back

using namespace std;
const int N = 30007;

int used[N];
vector<int> g[N];
int ma[N];
int qan = 0;
bool try_khun(int v){
	if (used[v])return false;
    used[v] = true;
	for (int to : g[v]){
		if (ma[to] == -1 || try_khun(ma[to])){
			//if (ma[to] == -1)qan++;
			ma[to] = v;
			return true;
		}
	}
	return false;
}
int main(){
	memset(ma, -1, sizeof(ma));
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= k; ++i){
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].ad(v);
	}

	int l = 1;
	long long ans = 0;
	int cnt = 0;

	for (int i = 1; i <= n; i++)
	{
		while (cnt == m)
		{
			assert(l <= i);

			bool minus = false;
			
			for (auto x : g[l])
			{
				if (ma[x] == l)
				{
					ma[x] = -1;
					minus = true;
					break;
				}
			}

			cnt -= minus;
			l++;
		}

		cnt += try_khun(i);

		if (cnt == m)
		{
			ans += n - i + 1;
		}

	}

	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:33:29: 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:36:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
                        ^

• Subtask 1: 20 / 100