Submission #345322

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
345322	2021-01-07T07:19:11 Z	maskoff	Marriage questions (IZhO14_marriage)	C++14	74 / 100	1500 ms	25576 KB

marriage

#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;
	int j = 1;
	for (int i = 1; i <= n; i++) {
		if (j == n + 1) if (check(i, n)) {res++; continue;}
		int p = check(i, j);
		while (j <= n && !p) {
		 	j++;
		 	p = check(i, j);
		}
		if (p) res += n - j + 1;
		else break;
	}
	cout << res;
  return 0;              
}

Subtask #1

74.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	23788 KB	Output is correct
2	Correct	18 ms	23788 KB	Output is correct
3	Correct	18 ms	23788 KB	Output is correct
4	Correct	17 ms	23788 KB	Output is correct
5	Correct	23 ms	23788 KB	Output is correct
6	Correct	19 ms	23820 KB	Output is correct
7	Correct	17 ms	23788 KB	Output is correct
8	Correct	17 ms	23788 KB	Output is correct
9	Correct	25 ms	23788 KB	Output is correct
10	Correct	17 ms	23916 KB	Output is correct
11	Correct	17 ms	23788 KB	Output is correct
12	Correct	15 ms	23788 KB	Output is correct
13	Correct	18 ms	23788 KB	Output is correct
14	Correct	17 ms	23928 KB	Output is correct
15	Correct	20 ms	23788 KB	Output is correct
16	Correct	18 ms	23788 KB	Output is correct
17	Correct	20 ms	23792 KB	Output is correct
18	Correct	20 ms	23788 KB	Output is correct
19	Correct	21 ms	23916 KB	Output is correct
20	Correct	19 ms	23916 KB	Output is correct
21	Correct	19 ms	23788 KB	Output is correct
22	Correct	19 ms	23920 KB	Output is correct
23	Correct	22 ms	23892 KB	Output is correct
24	Correct	18 ms	23916 KB	Output is correct
25	Correct	66 ms	24172 KB	Output is correct
26	Correct	28 ms	23916 KB	Output is correct
27	Correct	22 ms	23916 KB	Output is correct
28	Correct	19 ms	23916 KB	Output is correct
29	Correct	39 ms	24044 KB	Output is correct
30	Correct	39 ms	24044 KB	Output is correct
31	Execution timed out	1576 ms	24764 KB	Time limit exceeded
32	Correct	437 ms	24172 KB	Output is correct
33	Correct	30 ms	23832 KB	Output is correct
34	Correct	41 ms	23920 KB	Output is correct
35	Correct	670 ms	25324 KB	Output is correct
36	Correct	562 ms	25228 KB	Output is correct
37	Execution timed out	1588 ms	24684 KB	Time limit exceeded
38	Correct	1207 ms	25576 KB	Output is correct
39	Correct	1039 ms	24204 KB	Output is correct
40	Execution timed out	1568 ms	24428 KB	Time limit exceeded
41	Execution timed out	1577 ms	24556 KB	Time limit exceeded
42	Execution timed out	1581 ms	25004 KB	Time limit exceeded
43	Execution timed out	1519 ms	24952 KB	Time limit exceeded
44	Execution timed out	1556 ms	25196 KB	Time limit exceeded
45	Execution timed out	1564 ms	25160 KB	Time limit exceeded
46	Execution timed out	1556 ms	25364 KB	Time limit exceeded
47	Execution timed out	1588 ms	25356 KB	Time limit exceeded
48	Execution timed out	1571 ms	25524 KB	Time limit exceeded
49	Execution timed out	1564 ms	25548 KB	Time limit exceeded
50	Execution timed out	1552 ms	24156 KB	Time limit exceeded