Submission #5032

#	Time	Username	Problem	Language	Result	Execution time	Memory
5032		cki86201	Marriage questions (IZhO14_marriage)	C++98	96 / 100	1500 ms	2896 KiB

marriage

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

//for 72 point, O(NK+NM lg K);

typedef pair<int,int> Pi;
#define X first
#define Y second

vector <int> E[2020];

int n, m, mat, ans, now, mx;
int xy[30030], yx[2020], prev[30030];
int chk[30030], in;
int iter[30030];

bool match(int x)
{
	priority_queue <Pi, vector<Pi>, greater<Pi> >pq;
	for(size_t i=iter[x];i<E[x].size();i++){
		chk[E[x][i]] = in;
		pq.push(Pi(E[x][i],x));
		prev[E[x][i]] = -1;
	}
	while(!pq.empty()){
		Pi tmp = pq.top();
		pq.pop();
		if(!xy[tmp.X]){
			mx = max(mx, tmp.X);
			int s = tmp.X, e = tmp.Y;
			while(e!=-1){
				int save = yx[e];
				xy[s]=e, yx[e]=s;
				e=prev[s], s=save;
			}
			return true;
		}
		int v = xy[tmp.X];
		for(size_t i=iter[v];i<E[v].size();i++){
			if(chk[E[v][i]] == in)continue;
			chk[E[v][i]] = in;
			pq.push(Pi(E[v][i],v));
			prev[E[v][i]] = tmp.Y;
		}
	}
	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[y].push_back(x);
	}
	for(i=1;i<=m;i++)sort(E[i].begin(), E[i].end());
	for(i=1;i<=m;i++)if(match(in=i))mat++;
	while(mat==m){
		int t = min_element(yx+1,yx+1+m) - yx;
		ans += (yx[t] - now) * (n - mx + 1);
		now = yx[t];
		for(i=1;i<=m;i++)while(iter[i] != (int)E[i].size() && E[i][iter[i]]<=now)iter[i]++;
		xy[yx[t]] = 0, yx[t] = 0, mat--, in++;
		if(match(t))mat++;
	}
	printf("%d",ans);
	return 0;
}

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:55: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:58: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: 96 / 100