Submission #334734

#	Time	Username	Problem	Language	Result	Execution time	Memory
334734		limabeans	Marriage questions (IZhO14_marriage)	C++17	100 / 100	829 ms	25580 KiB

marriage

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


int n,m,k;
vector<int> g[maxn];



int match[maxn]; //husbands
int seen[maxn]; //daughters
queue<int> need;
int L, R;
int cloc = 0;




bool dfs(int at) {
    if (seen[at]==cloc) return false;
    seen[at]=cloc;
    for (int to: g[at]) {
	if (L<=to && to<=R) {
	    if (match[to]==-1 || dfs(match[to])) {
		match[to]=at;
		return true;
	    }
	}
    }
    return false;
}



int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m>>k;
    for (int i=0; i<k; i++) {
	int u,v;
	cin>>u>>v;
	--u; --v;
	g[v].push_back(u);
    }


    for (int i=0; i<n; i++) {
	match[i]=-1;	
    }

    for (int i=0; i<m; i++) {
	need.push(i);
    }

    ll ans = 0;

    for (int l=0,r=0; l<n; l++) {
	while (r<n) {
	    L=l; R=r;
	    while (need.size()) {
		++cloc;
		int at = need.front();
		if (dfs(at)) {
		    need.pop();
		} else {
		    break;
		}
	    }
	    if (need.size()) {
		++r;
	    } else {
		break;
	    }
	}

	if (need.size()) {
	    break;
	}

	ans += n-r;

	// get rid of husband l
	if (match[l]>=0) {
	    need.push(match[l]);
	    match[l]=-1;
	}
	
    }

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

• Subtask 1: 100 / 100