Submission #338785

#	Time	Username	Problem	Language	Result	Execution time	Memory
338785		Tosic	Marriage questions (IZhO14_marriage)	C++14	100 / 100	869 ms	1132 KiB

marriage

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;

long long ans;
int n,m, k, fMatch[maxn], iterNum[maxn], itV;

vector<vector<int> > gr;

bool dfs(int x, int& l, int& r){
	if(iterNum[x] == itV){
		return 0;
	}
	iterNum[x] = itV;
	for(auto i : gr[x]){
		if(i>=l and i <= r and (!fMatch[i] or dfs(fMatch[i], l, r)) ){
			fMatch[i] = x;
			return 1;
		}
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n >> m >> k;
	gr.resize(m+1, vector<int>());
	for(int i = 0; i < k; ++i){
		int a, b;
		cin >> a >> b;
		gr[b].push_back(a);
		//gr[b].push_back(a);
	}
	int j = 1;
	vector<int> notF;
	for(int i = 1; i <= m; ++i){
		notF.push_back(i);
	}
	for(int i = 1; i <= n; ++i){
		while(j <= n){

			if(!notF.size()){
				break;
			}
			for(int j0 = notF.size()-1; j0 >= 0; --j0){
				++itV;if(dfs(notF[j0], i, j)){
					notF.pop_back();
				} else {
					break;
				}
			}
			if(!notF.size()){
				break;
			}
			++j;
			//cerr << j << '\n';
		}
		if(notF.size()){
			break;
		}
		//cerr << j << '\n';
		ans += n+1-j;
		if(fMatch[i]){
			notF.push_back(fMatch[i]);
			fMatch[i] = 0;
		}
	}
	cout<<ans;
}

• Subtask 1: 100 / 100