oj.uz

Submission #340297

# Submission time Handle Problem Language Result Execution time Memory
340297 2020-12-27T11:47:32 Z _ani Marriage questions (IZhO14_marriage) C++17
42 / 100
 1500 ms 2796 KB 
#include <iostream>
#include <vector>
using namespace std;
vector<int> g[2005];
int used[2005];
bool FindHusband(int v, int l, int r)
{
	int mi = 1'000'000, miv = 0;
	for (auto to: g[v])
		if (!used[to] && to / 2 >= l && to / 2 <= r) {
			if (g[to].size() < mi)
			{
				mi = g[to].size();
				miv = to;
			}
		}
	if (miv == 0)return false;
	used[miv] = 1;
	return true;
}
int main()
{
	int n, m, k;
	cin >> n >> m >> k;
	while (k--)
	{
		int a, b;
		cin >> a >> b;
		//a-txa
		g[b * 2].push_back(a * 2 + 1);
		g[a * 2 + 1].push_back(b * 2);
	}
	int ans = 0;
	for (int l = 1; l <= n; l++)
		for (int r = l + m - 1; r <= n; r++)
		{
			bool ok = true;
			for (int i = 1; i <= m; i++)
				if (!FindHusband(2 * i, l, r))
				{
					ok = false;
					break;
				}
			if (ok)ans++;
			for (int k = l; k <= r; k++)
				used[k * 2 + 1] = 0;
		}
	cout << ans;
	return 0;
}

Compilation message

marriage.cpp: In function 'bool FindHusband(int, int, int)':
marriage.cpp:11:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   11 |    if (g[to].size() < mi)
      |        ~~~~~~~~~~~~~^~~~

Subtask #1
42.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Incorrect 1 ms 364 KB Output isn't correct
15 Incorrect 1 ms 364 KB Output isn't correct
16 Incorrect 1 ms 364 KB Output isn't correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Incorrect 26 ms 512 KB Output isn't correct
20 Incorrect 4 ms 364 KB Output isn't correct
21 Correct 1 ms 364 KB Output is correct
22 Incorrect 2 ms 364 KB Output isn't correct
23 Correct 4 ms 364 KB Output is correct
24 Correct 3 ms 364 KB Output is correct
25 Execution timed out 1575 ms 620 KB Time limit exceeded
26 Incorrect 872 ms 492 KB Output isn't correct
27 Correct 37 ms 492 KB Output is correct
28 Incorrect 85 ms 364 KB Output isn't correct
29 Correct 744 ms 620 KB Output is correct
30 Correct 546 ms 620 KB Output is correct
31 Execution timed out 1586 ms 1260 KB Time limit exceeded
32 Execution timed out 1531 ms 492 KB Time limit exceeded
33 Correct 43 ms 364 KB Output is correct
34 Incorrect 709 ms 516 KB Output isn't correct
35 Execution timed out 1572 ms 2156 KB Time limit exceeded
36 Execution timed out 1547 ms 2028 KB Time limit exceeded
37 Runtime error 1 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 32 ms 2796 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 2 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 1 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 1 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 2 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Runtime error 3 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Runtime error 5 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Runtime error 1 ms 620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 3 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 3 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)