Submission #345241

#	Time	Username	Problem	Language	Result	Execution time	Memory
345241		maskoff	Marriage questions (IZhO14_marriage)	C++14	80 / 100	1590 ms	25452 KiB

marriage

#include <bits/stdc++.h>

#define file ""

#define all(x) x.begin(), x.end()

#define sc second
#define fr first

#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;

const int N = 5e5 + 5;

int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};

int n, m, k, timer;
int used[N], mt[N], pr[N];
vector<int> g[N], all[N];

bool go(int v) {
	if (used[v] == timer) return false;
	used[v] = timer;
 	for (int to : g[v]) 
 		if (mt[to] == false) {
 		 	mt[to] = v;
 		 	pr[v] = to;
 		 	return true;
 		}    
	for (int to : g[v])
		if (go(mt[to])) {
		 	mt[to] = v;
		 	pr[v] = to;
		 	return true;
		}
	return false;
}

bool check(int y, int p) {
	fill (pr + 1, pr + 1 + m, false);
	for (int i = 1; i <= m; i++)
		g[i].clear();
	for (int i = y; i <= p; i++) {
	 	for (int j : all[i])
	 		g[j].pb(i);
	}
	for (int i = 1; i <= m; i++) {
		timer++;
		go(i);
	}
	int ok = true;
	for (int i = 1; i <= m; i++) 
		if (pr[i] == 0) ok = false;
		else mt[pr[i]] = false;
	return ok;
}

int main() {   
	ios_base :: sync_with_stdio(false);               
	cin.tie(nullptr);
	srand(time(nullptr));
	cin >> n >> m >> k;
	for (int x, y, i = 1; i <= k; i++) {
		cin >> x >> y;
	 	all[x].pb(y);
	}
	ll res = 0;
	for (int i = 1; i <= n; i++) {
		int l = i;
		int r = n;
		int ans = -1;
		while (l <= r) {
		 	int mid = l + r >> 1;
		 	if (check(i, mid)) ans = mid, r = mid - 1;
		 	else l = mid + 1;
		}
		if (ans == -1) break;
		else res += (n - ans + 1);
	}
	cout << res;
  return 0;              
}

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:82:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     int mid = l + r >> 1;
      |               ~~^~~

• Subtask 1: 80 / 100