oj.uz

Submission #91351

# Submission time Handle Problem Language Result Execution time Memory
91351 2018-12-27T08:33:42 Z Just_Solve_The_Problem Marriage questions (IZhO14_marriage) C++11
70 / 100
 1356 ms 1424 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define ok puts("ok");
#define ll long long
 
const int N = (int)2e3 + 7;
 
int n, m, k;
 
vector < int > gr[N];
pair < int, int > lr[N];
int used[N], mt[(int)3e4 + 7], prr[N], cnt = 1;
 
bool kuhn(int v) {
	if (used[v] == cnt) return false;
	used[v] = cnt;
	for (int i = lr[v].first; i < gr[v].size(); i++) {
		int to = gr[v][i];
		if (mt[to] == -1 || kuhn(mt[to])) {
			mt[to] = v;
			prr[v] = to;
			return true;
		}
	}
	return false;
}
 
int check(int l) {
	for (int i = 1; i <= m; i++) {
		while (lr[i].first < (int)gr[i].size() && gr[i][lr[i].first] < l) lr[i].first++;
	}
	memset(mt, -1, sizeof mt);
	memset(prr, -1, sizeof prr);
	int run = 1;
	while (run) {
		run = 0;
		for (int i = 1; i <= m; i++) {
			if (prr[i] == -1 && kuhn(i)) {
				run = 1;
			}
		}
		cnt++;
	}
	int mx = 0;
	for (int i = 1; i <= m; i++) {
		if (prr[i] == -1) {
			return n + 1;
		}
		mx = max(mx, prr[i]);
	}
	return mx;
}

bool kuhn1(int v) {
	if (used[v] == cnt) return false;
	used[v] = cnt;
	for (int i = lr[v].first; i <= lr[v].second; i++) {
		int to = gr[v][i];
		if (mt[to] == -1 || kuhn1(mt[to])) {
			mt[to] = v;
			prr[v] = to;
			return true;
		}
	}
	return false;
}

bool check1(int l, int r) {
	for (int i = 1; i <= m; i++) {
		while (lr[i].first < (int)gr[i].size() && gr[i][lr[i].first] < l) lr[i].first++;
		while (lr[i].first > 0 && gr[i][lr[i].first - 1] >= l) lr[i].first--;
		while (lr[i].second + 1 < (int)gr[i].size() && gr[i][lr[i].second + 1] <= r) lr[i].second++;
		while (lr[i].second >= 0 && gr[i][lr[i].second] > r) lr[i].second--;
	}
	memset(mt, -1, sizeof mt);
	memset(prr, -1, sizeof prr);
	int run = 1;
	while (run) {
		run = 0;
		for (int i = 1; i <= m; i++) {
			if (prr[i] == -1 && kuhn1(i)) {
				run = 1;
			}
		}
		cnt++;
	}
	for (int i = 1; i <= m; i++) {
		if (prr[i] == -1) {
			return 0;
		}
	}
	return 1;
}
 
main() {
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 1; i <= k; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		gr[b].push_back(a);
	}
	ll ans = 0;
	for (int i = 1; i <= m; i++) {
		sort(gr[i].begin(), gr[i].end());
		lr[i].second = -1;
		lr[i].first = gr[i].size();
	}
	if (n <= 1000 && m <= 500) {
		for (int i = 1; i <= n - m + 1; i++) {
			int lo = i;
			int hi = n + 1;
			while (hi - lo > 1) {
				int mid = (lo + hi) >> 1;
				if (check1(i, mid)) {
					hi = mid;
				} else {
					lo = mid;
				}
			}
			ans += (n - hi + 1);
		}
	} else {
		for (int i = 1; i <= n - m + 1; i++) {
			int res = check(i);
			//cout << i << ' ' << res << endl;
			ans += (n - res + 1);
		}
	}
	cout << ans << endl;
}

Compilation message

marriage.cpp: In function 'bool kuhn(int)':
marriage.cpp:19:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = lr[v].first; i < gr[v].size(); i++) {
                            ~~^~~~~~~~~~~~~~
marriage.cpp: At global scope:
marriage.cpp:97:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
marriage.cpp: In function 'int main()':
marriage.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 548 KB Output is correct
2 Correct 2 ms 548 KB Output is correct
3 Correct 2 ms 552 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Incorrect 2 ms 644 KB Output isn't correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 2 ms 644 KB Output is correct
11 Correct 2 ms 684 KB Output is correct
12 Correct 2 ms 684 KB Output is correct
13 Incorrect 2 ms 684 KB Output isn't correct
14 Correct 2 ms 744 KB Output is correct
15 Correct 2 ms 744 KB Output is correct
16 Correct 2 ms 760 KB Output is correct
17 Correct 2 ms 760 KB Output is correct
18 Correct 2 ms 792 KB Output is correct
19 Correct 7 ms 792 KB Output is correct
20 Correct 6 ms 792 KB Output is correct
21 Correct 4 ms 888 KB Output is correct
22 Correct 5 ms 888 KB Output is correct
23 Correct 5 ms 888 KB Output is correct
24 Correct 5 ms 888 KB Output is correct
25 Correct 84 ms 888 KB Output is correct
26 Correct 54 ms 888 KB Output is correct
27 Correct 29 ms 888 KB Output is correct
28 Correct 28 ms 888 KB Output is correct
29 Correct 35 ms 888 KB Output is correct
30 Correct 32 ms 888 KB Output is correct
31 Correct 1090 ms 1128 KB Output is correct
32 Correct 235 ms 1128 KB Output is correct
33 Correct 91 ms 1128 KB Output is correct
34 Correct 81 ms 1128 KB Output is correct
35 Correct 1356 ms 1404 KB Output is correct
36 Correct 1116 ms 1404 KB Output is correct
37 Incorrect 30 ms 1404 KB Output isn't correct
38 Incorrect 35 ms 1404 KB Output isn't correct
39 Incorrect 139 ms 1404 KB Output isn't correct
40 Correct 138 ms 1404 KB Output is correct
41 Incorrect 143 ms 1404 KB Output isn't correct
42 Incorrect 164 ms 1404 KB Output isn't correct
43 Incorrect 167 ms 1404 KB Output isn't correct
44 Incorrect 235 ms 1404 KB Output isn't correct
45 Incorrect 483 ms 1404 KB Output isn't correct
46 Incorrect 498 ms 1404 KB Output isn't correct
47 Incorrect 491 ms 1404 KB Output isn't correct
48 Incorrect 491 ms 1404 KB Output isn't correct
49 Incorrect 499 ms 1424 KB Output isn't correct
50 Incorrect 463 ms 1424 KB Output isn't correct