Submission #1125429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125429		Tsagana	Marriage questions (IZhO14_marriage)	C++20	100 / 100	660 ms	1864 KiB

marriage

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int L, R, T;
int mt[30005];
int vis[2005];

queue<int> q;
vector<int> adj[2005];

bool dfs(int s) {
	if (vis[s] == T) return 0;
	vis[s] = T;

	for (int i: adj[s]) {
		if (L > i || i > R) continue;
		if (!mt[i] || dfs(mt[i])) {mt[i] = s; return 1;}
	}
	return 0;
}

bool check() {
	while(!q.empty()) {
		int s = q.front(); q.pop();
		T++;
		if (!dfs(s)) {
			q.push(s);
			return 0;
		}
	}
	return 1;
}

void solve () {
	int N, M, Q; cin >> N >> M >> Q;
	
	while (Q--) {int x, y; cin >> x >> y; adj[y].pb(x);}
	for (int i = 1; i <= M; i++) q.push(i);

	int ans = 0; R = 1;
	for (L = 1; L <= N; L++) {
		while (R <= N && !check()) R++;
		ans += N - R + 1;
		if (mt[L]) {
			q.push(mt[L]);
			mt[L] = 0;
		}
	}
	cout << ans;
}
signed main() {IOS solve(); return 0;}

• Subtask 1: 100 / 100