Submission #345303

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
345303	2021-01-07T07:14:24 Z	maskoff	Marriage questions (IZhO14_marriage)	C++14	74 / 100	1500 ms	25324 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++) {
		while (j <= n && !check(i, j)) {
		 	j++;
		}
		if (check(i, j)) res += n - j + 1;
		else break;
	}
	cout << res;
  return 0;              
}

Subtask #1

74.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	23788 KB	Output is correct
2	Correct	16 ms	23784 KB	Output is correct
3	Correct	15 ms	23788 KB	Output is correct
4	Correct	16 ms	23900 KB	Output is correct
5	Correct	16 ms	23808 KB	Output is correct
6	Correct	18 ms	23792 KB	Output is correct
7	Correct	16 ms	23788 KB	Output is correct
8	Correct	16 ms	23788 KB	Output is correct
9	Correct	17 ms	23788 KB	Output is correct
10	Correct	17 ms	23788 KB	Output is correct
11	Correct	16 ms	23916 KB	Output is correct
12	Correct	17 ms	23792 KB	Output is correct
13	Correct	19 ms	23788 KB	Output is correct
14	Correct	16 ms	23788 KB	Output is correct
15	Correct	15 ms	23788 KB	Output is correct
16	Correct	19 ms	23788 KB	Output is correct
17	Correct	16 ms	23788 KB	Output is correct
18	Correct	15 ms	23788 KB	Output is correct
19	Correct	21 ms	23996 KB	Output is correct
20	Correct	17 ms	23788 KB	Output is correct
21	Correct	17 ms	23788 KB	Output is correct
22	Correct	15 ms	23788 KB	Output is correct
23	Correct	20 ms	23916 KB	Output is correct
24	Correct	15 ms	23912 KB	Output is correct
25	Correct	74 ms	23916 KB	Output is correct
26	Correct	28 ms	23916 KB	Output is correct
27	Correct	20 ms	23920 KB	Output is correct
28	Correct	19 ms	23788 KB	Output is correct
29	Correct	41 ms	23916 KB	Output is correct
30	Correct	35 ms	23996 KB	Output is correct
31	Execution timed out	1561 ms	24392 KB	Time limit exceeded
32	Correct	393 ms	24044 KB	Output is correct
33	Correct	28 ms	23916 KB	Output is correct
34	Correct	46 ms	23916 KB	Output is correct
35	Correct	961 ms	25084 KB	Output is correct
36	Correct	705 ms	24940 KB	Output is correct
37	Execution timed out	1600 ms	24300 KB	Time limit exceeded
38	Correct	1375 ms	25324 KB	Output is correct
39	Correct	1421 ms	24172 KB	Output is correct
40	Execution timed out	1548 ms	24304 KB	Time limit exceeded
41	Execution timed out	1589 ms	24428 KB	Time limit exceeded
42	Execution timed out	1600 ms	24428 KB	Time limit exceeded
43	Execution timed out	1591 ms	24556 KB	Time limit exceeded
44	Execution timed out	1560 ms	24852 KB	Time limit exceeded
45	Execution timed out	1549 ms	24816 KB	Time limit exceeded
46	Execution timed out	1578 ms	25196 KB	Time limit exceeded
47	Execution timed out	1539 ms	25056 KB	Time limit exceeded
48	Execution timed out	1566 ms	25012 KB	Time limit exceeded
49	Execution timed out	1576 ms	25068 KB	Time limit exceeded
50	Execution timed out	1588 ms	24104 KB	Time limit exceeded