Submission #345388

#	Time	Username	Problem	Language	Result	Execution time	Memory
345388		maskoff	Marriage questions (IZhO14_marriage)	C++14	88 / 100	1599 ms	25440 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], s[N];
vector<int> g[N], all[N];

bool go(int v) {
	if (used[v] == timer) return false;
	used[v] = timer;

 	for (int i = s[v]; i < g[v].size(); i++) {
  	int to = g[v][i];
 		if (mt[to] == false) {
 		 	mt[to] = v;
 		 	pr[v] = to;
 		 	return true;
 		}
 	}
 	  
 	for (int i = s[v]; i < g[v].size(); i++) {
 		int to = g[v][i];
		if (go(mt[to])) {
		 	mt[to] = v;
		 	pr[v] = to;
		 	return true;
		}
	}

	return false;
}

bool check(int p) {
	fill (pr + 1, pr + 1 + m, false);

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

bool clear(int x) {
 	for (int j : all[x]) 
 		s[j]++;
 	fill (pr + 1, pr + 1 + m, false);
 	for (int i = 1; i <= m; i++) {
 		timer++;
 		go(i);
 	}
 	bool ok = true;
	for (int i = 1; i <= m; i++) 
		if (pr[i] == 0) ok = false;
		else mt[pr[i]] = 0;
	
	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;
	int j = 1;
	bool p = check(1);
	for (int i = 1; i <= n; i++) {
		while (j <= n && !p) {
			j++;
			if (j == n + 1) break;
			p = check(j);
	 	}
	 	if (p) res += n - j + 1;
	 	else break;
	 	p = clear(i);
	}
	cout << res;
  return 0;              
}

Compilation message (stderr)

marriage.cpp: In function 'bool go(int)':
marriage.cpp:35:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int i = s[v]; i < g[v].size(); i++) {
      |                      ~~^~~~~~~~~~~~~
marriage.cpp:44:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for (int i = s[v]; i < g[v].size(); i++) {
      |                      ~~^~~~~~~~~~~~~

• Subtask 1: 88 / 100