oj.uz

답안 #39034

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39034 2018-01-09T06:07:50 Z RockyB 결혼 문제 (IZhO14_marriage) C++14
22 / 100
 149 ms 3552 KB 
/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)3e4 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n, m, k;
vector <int> g[N];

int p[N];
bool was[N];
int dfs(int v, int R) {
	if (was[v]) return 0;
	was[v] = 1;
	for (auto to : g[v]) {
		if (!(to <= R)) continue; 
		if (p[to] == -1 || dfs(p[to], R)) {
			p[to] = v;
			return 1;
		}
	}
	return 0;
}
int ok(int R) {
	R += m;
	memset(p, -1, sizeof(p));
	for (int i = 1; i <= m; i++) {
		memset(was, 0, sizeof(was));
		dfs(i, R);
	}
	int cnt = 0, last = -1;
	for (int i = m + 1; i <= n + m; i++) {
		cnt += p[i] != -1;
		if (p[i] != -1 && last == -1) last = i;
		cerr << p[i] << ' ';
	}
	cerr << nl;
	if (cnt == m) return last - (m + 1) + 1;
	return 0;
}
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	Kazakhstan
	cin >> n >> m >> k;
	for (int i = 1; i <= k; i++) {
		int a, b;
		cin >> b >> a;
		g[a].pb(b + m);
	}
	for (int i = 1; i <= m; i++) {
		//sort(all(g[i]));
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += ok(i);
	}
	cout << ans;
	ioi
}

Subtask #1
22.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 3024 KB Output isn't correct
2 Incorrect 0 ms 3024 KB Output isn't correct
3 Incorrect 3 ms 3024 KB Output isn't correct
4 Correct 0 ms 3024 KB Output is correct
5 Correct 0 ms 3024 KB Output is correct
6 Correct 0 ms 3024 KB Output is correct
7 Incorrect 3 ms 3024 KB Output isn't correct
8 Correct 0 ms 3024 KB Output is correct
9 Correct 0 ms 3024 KB Output is correct
10 Correct 0 ms 3024 KB Output is correct
11 Correct 0 ms 3024 KB Output is correct
12 Correct 0 ms 3024 KB Output is correct
13 Incorrect 0 ms 3024 KB Output isn't correct
14 Incorrect 3 ms 3024 KB Output isn't correct
15 Incorrect 13 ms 3024 KB Output isn't correct
16 Correct 6 ms 3024 KB Output is correct
17 Incorrect 0 ms 3024 KB Output isn't correct
18 Incorrect 9 ms 3024 KB Output isn't correct
19 Incorrect 26 ms 3024 KB Output isn't correct
20 Incorrect 26 ms 3024 KB Output isn't correct
21 Correct 39 ms 3024 KB Output is correct
22 Correct 53 ms 3024 KB Output is correct
23 Incorrect 63 ms 3024 KB Output isn't correct
24 Incorrect 19 ms 3024 KB Output isn't correct
25 Runtime error 49 ms 3024 KB Execution timed out (wall clock limit exceeded)
26 Runtime error 83 ms 3024 KB Execution timed out (wall clock limit exceeded)
27 Runtime error 66 ms 3024 KB Execution timed out (wall clock limit exceeded)
28 Runtime error 83 ms 3024 KB Execution timed out (wall clock limit exceeded)
29 Runtime error 76 ms 3024 KB Execution timed out (wall clock limit exceeded)
30 Runtime error 89 ms 3024 KB Execution timed out (wall clock limit exceeded)
31 Runtime error 103 ms 3288 KB Execution timed out (wall clock limit exceeded)
32 Runtime error 66 ms 3024 KB Execution timed out (wall clock limit exceeded)
33 Runtime error 66 ms 3024 KB Execution timed out (wall clock limit exceeded)
34 Runtime error 79 ms 3024 KB Execution timed out (wall clock limit exceeded)
35 Runtime error 73 ms 3552 KB Execution timed out (wall clock limit exceeded)
36 Runtime error 66 ms 3552 KB Execution timed out (wall clock limit exceeded)
37 Runtime error 83 ms 3288 KB Execution timed out (wall clock limit exceeded)
38 Runtime error 76 ms 3552 KB Execution timed out (wall clock limit exceeded)
39 Runtime error 96 ms 3024 KB Execution timed out (wall clock limit exceeded)
40 Runtime error 76 ms 3024 KB Execution timed out (wall clock limit exceeded)
41 Runtime error 29 ms 3156 KB Execution timed out (wall clock limit exceeded)
42 Runtime error 53 ms 3156 KB Execution timed out (wall clock limit exceeded)
43 Runtime error 66 ms 3288 KB Execution timed out (wall clock limit exceeded)
44 Runtime error 96 ms 3552 KB Execution timed out (wall clock limit exceeded)
45 Runtime error 63 ms 3156 KB Execution timed out (wall clock limit exceeded)
46 Runtime error 113 ms 3552 KB Execution timed out (wall clock limit exceeded)
47 Runtime error 76 ms 3552 KB Execution timed out (wall clock limit exceeded)
48 Runtime error 149 ms 3552 KB Execution timed out (wall clock limit exceeded)
49 Runtime error 123 ms 3552 KB Execution timed out (wall clock limit exceeded)
50 Runtime error 43 ms 3024 KB Execution timed out (wall clock limit exceeded)