Submission #5030

#	Time	Username	Problem	Language	Result	Execution time	Memory
5030		cki86201	Marriage questions (IZhO14_marriage)	C++98	62 / 100	1500 ms	3052 KiB

marriage

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

//for 72point, O(N(K+M));

vector <int> E[30030];

int n, m, now, mat, ans, prev;
int yx[2020];
int vis[30030],in;

bool dfs(int x)
{
	vis[x] = in;
	for(size_t i=0;i<E[x].size();i++)
		if(!yx[E[x][i]] || (vis[yx[E[x][i]]] != in && dfs(yx[E[x][i]]))){
			yx[E[x][i]] = x;
			return true;
		}
	return false;
}

int main()
{
	int k, i;
	scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=k;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		E[x].push_back(y);
	}
	for(i=1;i<=n;i++){
		if(dfs(in=i))mat++;
		if(mat == m){
			int mn = 1;
			for(int j=2;j<=m;j++)if(yx[j] < yx[mn])mn = j;
			ans += (yx[mn] - prev) * (n-i+1);
			prev = yx[mn];
			yx[mn] = 0;
			mat--;
		}
	}
	if(mat == m-1){
		int mx=1, mn=n;
		for(int j=1;j<=m;j++)mx=max(mx,yx[j]), mn=min(mn,yx[j]?yx[j]:n);
		ans += (mn - prev - 1) * (n - mx + 1);
	}
	printf("%d",ans);
	return 0;
}

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:28:26: 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:31:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
                      ^

• Subtask 1: 62 / 100