oj.uz

Submission #501868

# Submission time Handle Problem Language Result Execution time Memory
501868 2022-01-04T17:43:00 Z keta_tsimakuridze Marriage questions (IZhO14_marriage) C++17
80 / 100
 1500 ms 5356 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1740 KB Output is correct
2 Correct 1 ms 1824 KB Output is correct
3 Correct 1 ms 1824 KB Output is correct
4 Correct 1 ms 1740 KB Output is correct
5 Correct 1 ms 1740 KB Output is correct
6 Correct 1 ms 1824 KB Output is correct
7 Correct 1 ms 1740 KB Output is correct
8 Correct 2 ms 1804 KB Output is correct
9 Correct 1 ms 1824 KB Output is correct
10 Correct 1 ms 1740 KB Output is correct
11 Correct 1 ms 1820 KB Output is correct
12 Correct 1 ms 1740 KB Output is correct
13 Correct 1 ms 1740 KB Output is correct
14 Correct 1 ms 1740 KB Output is correct
15 Correct 1 ms 1824 KB Output is correct
16 Correct 1 ms 1824 KB Output is correct
17 Correct 2 ms 1740 KB Output is correct
18 Correct 2 ms 1740 KB Output is correct
19 Correct 3 ms 1868 KB Output is correct
20 Correct 2 ms 1740 KB Output is correct
21 Correct 1 ms 1740 KB Output is correct
22 Correct 1 ms 1824 KB Output is correct
23 Correct 2 ms 1740 KB Output is correct
24 Correct 1 ms 1740 KB Output is correct
25 Correct 22 ms 2100 KB Output is correct
26 Incorrect 6 ms 1912 KB Output isn't correct
27 Correct 1 ms 1824 KB Output is correct
28 Correct 1 ms 1832 KB Output is correct
29 Correct 16 ms 2028 KB Output is correct
30 Correct 16 ms 1956 KB Output is correct
31 Correct 206 ms 3072 KB Output is correct
32 Incorrect 37 ms 1996 KB Output isn't correct
33 Correct 1 ms 1868 KB Output is correct
34 Correct 5 ms 1824 KB Output is correct
35 Correct 282 ms 4104 KB Output is correct
36 Correct 234 ms 3968 KB Output is correct
37 Correct 527 ms 3224 KB Output is correct
38 Correct 596 ms 4716 KB Output is correct
39 Correct 60 ms 2132 KB Output is correct
40 Correct 27 ms 2484 KB Output is correct
41 Incorrect 393 ms 2844 KB Output isn't correct
42 Correct 1105 ms 3248 KB Output is correct
43 Execution timed out 1552 ms 3604 KB Time limit exceeded
44 Execution timed out 1587 ms 4556 KB Time limit exceeded
45 Incorrect 420 ms 3840 KB Output isn't correct
46 Execution timed out 1572 ms 4804 KB Time limit exceeded
47 Execution timed out 1573 ms 5356 KB Time limit exceeded
48 Execution timed out 1539 ms 5176 KB Time limit exceeded
49 Execution timed out 1566 ms 4828 KB Time limit exceeded
50 Correct 63 ms 2304 KB Output is correct