oj.uz

Submission #345241

# Submission time Handle Problem Language Result Execution time Memory
345241 2021-01-07T07:01:05 Z maskoff Marriage questions (IZhO14_marriage) C++14
80 / 100
 1500 ms 25452 KB 
#include <bits/stdc++.h>

#define file ""

#define all(x) x.begin(), x.end()

#define sc second
#define fr first

#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;

const int N = 5e5 + 5;

int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};

int n, m, k, timer;
int used[N], mt[N], pr[N];
vector<int> g[N], all[N];

bool go(int v) {
	if (used[v] == timer) return false;
	used[v] = timer;
 	for (int to : g[v]) 
 		if (mt[to] == false) {
 		 	mt[to] = v;
 		 	pr[v] = to;
 		 	return true;
 		}    
	for (int to : g[v])
		if (go(mt[to])) {
		 	mt[to] = v;
		 	pr[v] = to;
		 	return true;
		}
	return false;
}

bool check(int y, int p) {
	fill (pr + 1, pr + 1 + m, false);
	for (int i = 1; i <= m; i++)
		g[i].clear();
	for (int i = y; i <= p; i++) {
	 	for (int j : all[i])
	 		g[j].pb(i);
	}
	for (int i = 1; i <= m; i++) {
		timer++;
		go(i);
	}
	int ok = true;
	for (int i = 1; i <= m; i++) 
		if (pr[i] == 0) ok = false;
		else mt[pr[i]] = false;
	return ok;
}

int main() {   
	ios_base :: sync_with_stdio(false);               
	cin.tie(nullptr);
	srand(time(nullptr));
	cin >> n >> m >> k;
	for (int x, y, i = 1; i <= k; i++) {
		cin >> x >> y;
	 	all[x].pb(y);
	}
	ll res = 0;
	for (int i = 1; i <= n; i++) {
		int l = i;
		int r = n;
		int ans = -1;
		while (l <= r) {
		 	int mid = l + r >> 1;
		 	if (check(i, mid)) ans = mid, r = mid - 1;
		 	else l = mid + 1;
		}
		if (ans == -1) break;
		else res += (n - ans + 1);
	}
	cout << res;
  return 0;              
}

Compilation message

marriage.cpp: In function 'int main()':
marriage.cpp:82:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23792 KB Output is correct
2 Correct 15 ms 23788 KB Output is correct
3 Correct 15 ms 23900 KB Output is correct
4 Correct 17 ms 23788 KB Output is correct
5 Correct 17 ms 23788 KB Output is correct
6 Correct 15 ms 23788 KB Output is correct
7 Correct 19 ms 23788 KB Output is correct
8 Correct 16 ms 23788 KB Output is correct
9 Correct 16 ms 23788 KB Output is correct
10 Correct 18 ms 23788 KB Output is correct
11 Correct 17 ms 23788 KB Output is correct
12 Correct 20 ms 23788 KB Output is correct
13 Correct 19 ms 23916 KB Output is correct
14 Correct 15 ms 23788 KB Output is correct
15 Correct 15 ms 23788 KB Output is correct
16 Correct 15 ms 23788 KB Output is correct
17 Correct 18 ms 23788 KB Output is correct
18 Correct 22 ms 23788 KB Output is correct
19 Correct 25 ms 23916 KB Output is correct
20 Correct 21 ms 23916 KB Output is correct
21 Correct 17 ms 23788 KB Output is correct
22 Correct 17 ms 23788 KB Output is correct
23 Correct 17 ms 23916 KB Output is correct
24 Correct 16 ms 23788 KB Output is correct
25 Correct 301 ms 24044 KB Output is correct
26 Correct 70 ms 23944 KB Output is correct
27 Correct 18 ms 23916 KB Output is correct
28 Correct 28 ms 23788 KB Output is correct
29 Correct 71 ms 23916 KB Output is correct
30 Correct 59 ms 23916 KB Output is correct
31 Execution timed out 1586 ms 24556 KB Time limit exceeded
32 Correct 267 ms 24044 KB Output is correct
33 Correct 21 ms 23916 KB Output is correct
34 Correct 81 ms 23916 KB Output is correct
35 Execution timed out 1571 ms 24928 KB Time limit exceeded
36 Execution timed out 1578 ms 24940 KB Time limit exceeded
37 Execution timed out 1590 ms 24540 KB Time limit exceeded
38 Correct 779 ms 25324 KB Output is correct
39 Execution timed out 1558 ms 24172 KB Time limit exceeded
40 Correct 26 ms 24172 KB Output is correct
41 Execution timed out 1544 ms 24464 KB Time limit exceeded
42 Correct 178 ms 24544 KB Output is correct
43 Correct 384 ms 24668 KB Output is correct
44 Correct 528 ms 25196 KB Output is correct
45 Execution timed out 1568 ms 24684 KB Time limit exceeded
46 Execution timed out 1564 ms 25324 KB Time limit exceeded
47 Correct 814 ms 25436 KB Output is correct
48 Correct 713 ms 25452 KB Output is correct
49 Execution timed out 1532 ms 25400 KB Time limit exceeded
50 Execution timed out 1538 ms 24220 KB Time limit exceeded