Submission #501868

#	Time	Username	Problem	Language	Result	Execution time	Memory
501868		keta_tsimakuridze	Marriage questions (IZhO14_marriage)	C++17	80 / 100	1587 ms	5356 KiB

marriage

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 3e4 + 2e3 + 5, mod = 1e9 + 7; // !
int t, f[N], sz, cur, match[N];
vector<int> x[N];
vector<int> V[N];
bool try_dfs(int u) {
	if(cur == f[u]) return 0;
	f[u] = cur;
	for(int i = 0; i < V[u].size(); i++) {
		if(!match[V[u][i]] || try_dfs(match[V[u][i]])) {
			match[u] = V[u][i];
			match[V[u][i]] = u;
			return 1;
		}
	}
	return 0;
}
void add(int u) {
	cur++; 
	sz += try_dfs(u);
}
void remove(int u) {
	cur++;
	if(!match[u]) return;
	sz --;
	match[match[u]] = 0;
	sz += try_dfs(match[u]);
}
main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	for(int i = 1; i <= k; i++) {
		int u, v;
		cin >> u >> v; swap(u, v);
		x[v + m].push_back(u);
	}
	int r = m + 1;
	ll ans = 0;
	for(int l = 1 + m; l <= n + m; l++) {
		
		while(sz < m && r <= n + m) {
			for(int i = 0; i < x[r].size(); i++) V[r].push_back(x[r][i]), V[x[r][i]].push_back(r);
			add(r);
			r++;
		}
		if(sz == m) ans += n + m - r + 2; 
		remove(l);
	}
	cout << ans;
}

Compilation message (stderr)

marriage.cpp: In function 'bool try_dfs(int)':
marriage.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
marriage.cpp: At global scope:
marriage.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main(){
      | ^~~~
marriage.cpp: In function 'int main()':
marriage.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    for(int i = 0; i < x[r].size(); i++) V[r].push_back(x[r][i]), V[x[r][i]].push_back(r);
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 80 / 100