oj.uz

Submission #501869

# Submission time Handle Problem Language Result Execution time Memory
501869 2022-01-04T17:44:36 Z keta_tsimakuridze Marriage questions (IZhO14_marriage) C++14
80 / 100
 1500 ms 4364 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]) { match[u] = 12314; 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:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main(){
      | ^~~~
marriage.cpp: In function 'int main()':
marriage.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    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 1740 KB Output is correct
3 Correct 1 ms 1740 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 1740 KB Output is correct
7 Correct 1 ms 1740 KB Output is correct
8 Correct 1 ms 1740 KB Output is correct
9 Correct 1 ms 1740 KB Output is correct
10 Correct 1 ms 1740 KB Output is correct
11 Correct 1 ms 1816 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 1740 KB Output is correct
16 Correct 1 ms 1740 KB Output is correct
17 Correct 1 ms 1740 KB Output is correct
18 Correct 1 ms 1740 KB Output is correct
19 Correct 2 ms 1868 KB Output is correct
20 Correct 1 ms 1740 KB Output is correct
21 Correct 1 ms 1740 KB Output is correct
22 Correct 2 ms 1740 KB Output is correct
23 Correct 2 ms 1740 KB Output is correct
24 Correct 1 ms 1740 KB Output is correct
25 Correct 21 ms 2080 KB Output is correct
26 Incorrect 6 ms 1868 KB Output isn't correct
27 Correct 1 ms 1740 KB Output is correct
28 Correct 1 ms 1740 KB Output is correct
29 Correct 16 ms 2000 KB Output is correct
30 Correct 13 ms 1996 KB Output is correct
31 Correct 197 ms 2696 KB Output is correct
32 Incorrect 32 ms 1868 KB Output isn't correct
33 Correct 1 ms 1868 KB Output is correct
34 Correct 6 ms 1868 KB Output is correct
35 Correct 253 ms 3380 KB Output is correct
36 Correct 199 ms 3324 KB Output is correct
37 Correct 566 ms 2844 KB Output is correct
38 Correct 551 ms 3780 KB Output is correct
39 Correct 66 ms 2260 KB Output is correct
40 Correct 32 ms 2380 KB Output is correct
41 Incorrect 442 ms 2580 KB Output isn't correct
42 Correct 1115 ms 2976 KB Output is correct
43 Execution timed out 1578 ms 3140 KB Time limit exceeded
44 Execution timed out 1585 ms 3712 KB Time limit exceeded
45 Incorrect 848 ms 3536 KB Output isn't correct
46 Execution timed out 1591 ms 3948 KB Time limit exceeded
47 Execution timed out 1579 ms 4364 KB Time limit exceeded
48 Execution timed out 1587 ms 4328 KB Time limit exceeded
49 Execution timed out 1590 ms 3884 KB Time limit exceeded
50 Correct 60 ms 2308 KB Output is correct