답안 #388184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
388184	2021-04-10T12:33:11 Z	BorisBarca	Skandi (COCI20_skandi)	C++14	55 / 110	754 ms	34824 KB

skandi

/*
$$$$$$$\                      $$\           $$$$$$$\
$$  __$$\                     \__|          $$  __$$\
$$ |  $$ | $$$$$$\   $$$$$$\  $$\  $$$$$$$\ $$ |  $$ | $$$$$$\   $$$$$$\   $$$$$$$\ $$$$$$\
$$$$$$$\ |$$  __$$\ $$  __$$\ $$ |$$  _____|$$$$$$$\ | \____$$\ $$  __$$\ $$  _____|\____$$\
$$  __$$\ $$ /  $$ |$$ |  \__|$$ |\$$$$$$\  $$  __$$\  $$$$$$$ |$$ |  \__|$$ /      $$$$$$$ |
$$ |  $$ |$$ |  $$ |$$ |      $$ | \____$$\ $$ |  $$ |$$  __$$ |$$ |      $$ |     $$  __$$ |
$$$$$$$  |\$$$$$$  |$$ |      $$ |$$$$$$$  |$$$$$$$  |\$$$$$$$ |$$ |      \$$$$$$$\\$$$$$$$ |
\_______/  \______/ \__|      \__|\_______/ \_______/  \_______|\__|       \_______|\_______|
*/
#include <bits/stdc++.h>

using namespace std;

#define PB push_back
#define MP make_pair
#define INS insert
#define LB lower_bound
#define UB upper_bound
#define pii pair <int,int>
#define pll pair <long long, long long>
#define X first
#define Y second
#define _ << " " <<
#define sz(x) (int)x.size()
#define all(a) (a).begin(),(a).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (a); i > (b); --i)
#define FORA(i, x) for (auto &i : x)
#define REP(i, n) FOR(i, 0, n)
#define BITS(x) __builtin_popcount(x)
#define SQ(a) (a) * (a)
#define TRACE(x) cout << #x " = " << (x) << '\n';
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define umap unordered_map

typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <pii> vpi;
typedef vector <ll> vll;
typedef vector <pll> vpl;
typedef vector <double> vd;
typedef vector <ld> vld;
typedef vector<string> vs;
//((float) t)/CLOCKS_PER_SEC

const int MOD = 1e9 + 2015;
const double PI = acos(-1);
const int INF = 1e9 + 10;
const ll INFL = 1e18 + 10;
const int ABC = 30;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dox[] = {-1, 1, 0, 0, -1, -1, 1, 1};
const int doy[] = {0, 0, -1, 1, -1, 1, -1, 1};

inline int sum(int a, int b){
	if (a + b < 0)
		return (a + b + MOD) % MOD;
	return (a + b) % MOD;
}

inline void add(int &a, int b){
	a = sum(a, b);
}

inline int mul(int a, int b){
	return (ll)a * (ll)b % MOD;
}

inline int sub(int a, int b){
	return (a - b + MOD) % MOD;
}

inline int fast_pot(ll pot, ll n){
	ll ret = 1;
	while (n){
		if (n & 1LL)
			ret = (ret * pot) % MOD;
		pot = (pot * pot) % MOD;
		n >>= 1LL;
	}
	return ret;
}

inline int divide(int a, int b){
	return mul(a, fast_pot(b, MOD - 2));
}

ll lcm(ll a, ll b){
	return abs(a * b) / __gcd(a, b);
}

inline double ccw(pii A, pii B, pii C){
	return (A.X * B.Y) - (A.Y * B.X) + (B.X * C.Y) - (B.Y * C.X) + (C.X * A.Y) - (C.Y * A.X);
}

inline int CCW(pii A, pii B, pii C){
	double val = ccw(A, B, C);
	double eps = max(max(abs(A.X), abs(A.Y)), max(max(abs(B.X), abs(B.Y)), max(abs(C.X), abs(C.Y)))) / 1e9;
	if (val <= -eps)
		return -1;
	if (val >= eps)
		return 1;
	return 0;
}

void to_upper(string &x){
	REP(i, sz(x))
		x[i] = toupper(x[i]);
}

void to_lower(string &x){
	REP(i, sz(x))
		x[i] = tolower(x[i]);
}

string its(ll x){
	if (x == 0)
		return "0";
	string ret = "";
	while (x > 0){
		ret += (x % 10) + '0';
		x /= 10;
	}
	reverse(all(ret));
	return ret;
}

ll sti(string s){
	ll ret = 0;
	REP(i, sz(s)){
		ret *= 10;
		ret += (s[i] - '0');
	}
	return ret;
}

const int N = 505;
const int NIL = 0;

int n, m, idx[N][N], h[N][N], v[N][N], cnt, pair_u[3 * N * N], pair_v[3 * N * N], dist[3 * N * N];
string mat[N];
umap <int, umap <int, int>> e;

bool bfs(){
	queue <int> q;
	FOR(u, 1, cnt){
		if (pair_u[u] == NIL){
			dist[u] = 0;
			q.push(u);
		} else 
			dist[u] = INF;
	}
	dist[NIL] = INF;
	while (sz(q)){
		int u = q.front(); q.pop();
		if (dist[u] < dist[NIL]){
			FORA(v, e[u]){
				if (dist[pair_v[v.X]] == INF){
					dist[pair_v[v.X]] = dist[u] + 1;
					q.push(pair_v[v.X]);
				}
			}
		}
	}
	return (dist[NIL] != INF);
}

bool dfs(int u){
	if (u != NIL){
		FORA(v, e[u]){
			if (dist[pair_v[v.X]] == dist[u] + 1){
				if (dfs(pair_v[v.X])){
					pair_u[u] = v.X;
					pair_v[v.X] = u;
					return true;
				}
			}
		}
		dist[u] = INF;
		return false;
	}
	return true;
}

int hopcroft_karp(){
	FOR(u, 1, cnt)
		pair_u[u] = NIL;
	FOR(v, cnt, 2 * cnt + 1)
		pair_v[v] = NIL;
	int ret = 0;
	while (bfs()){
		FOR(u, 1, cnt){
			if (pair_u[u] == NIL){
				if (dfs(u))
					ret++;
			}
		}
	}
	return ret;
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	REP(i, n)
		cin >> mat[i];

	cnt = 1;
	REP(i, n)
		REP(j, m)
			if (mat[i][j] == '1')
				idx[i][j] = cnt++;

	REP(i, n){
		int tmp = 0;
		REP(j, m){
			if (mat[i][j] == '1'){
				tmp = idx[i][j];
			}
			h[i][j] = tmp;
		}
	}

	REP(j, m){
		int tmp = 0;
		REP(i, n){
			if (mat[i][j] == '1'){
				tmp = idx[i][j];
			}
			v[i][j] = tmp + cnt;
		}
	}

	REP(i, n){
		REP(j, m){
			if (mat[i][j] == '0'){
				e[h[i][j]][v[i][j]] = 1;
				e[v[i][j]][h[i][j]] = 1;
			}
		}
	}

	cout << hopcroft_karp() << '\n';
	
	return 0;
}

Subtask #1
9.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
2	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
3	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
4	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
5	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
6	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
7	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
8	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
9	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
10	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
11	Partially correct	1 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
12	Partially correct	1 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
13	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
14	Partially correct	1 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
15	Partially correct	1 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
16	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
17	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
18	Partially correct	1 ms	336 KB	First line is correct, but the reconstruction is not properly formatted.
19	Partially correct	1 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
20	Partially correct	1 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
21	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
22	Partially correct	1 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
23	Partially correct	1 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.

Subtask #2
16.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	3 ms	2892 KB	First line is correct, but the reconstruction is not properly formatted.
2	Partially correct	1 ms	1484 KB	First line is correct, but the reconstruction is not properly formatted.
3	Partially correct	2 ms	2636 KB	First line is correct, but the reconstruction is not properly formatted.
4	Partially correct	1 ms	1356 KB	First line is correct, but the reconstruction is not properly formatted.
5	Partially correct	1 ms	1356 KB	First line is correct, but the reconstruction is not properly formatted.
6	Partially correct	1 ms	972 KB	First line is correct, but the reconstruction is not properly formatted.
7	Partially correct	1 ms	844 KB	First line is correct, but the reconstruction is not properly formatted.
8	Partially correct	2 ms	1616 KB	First line is correct, but the reconstruction is not properly formatted.
9	Partially correct	3 ms	3660 KB	First line is correct, but the reconstruction is not properly formatted.
10	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
11	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
12	Partially correct	4 ms	3788 KB	First line is correct, but the reconstruction is not properly formatted.
13	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
14	Partially correct	4 ms	3980 KB	First line is correct, but the reconstruction is not properly formatted.
15	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
16	Partially correct	4 ms	3952 KB	First line is correct, but the reconstruction is not properly formatted.
17	Partially correct	4 ms	3788 KB	First line is correct, but the reconstruction is not properly formatted.
18	Partially correct	4 ms	3788 KB	First line is correct, but the reconstruction is not properly formatted.
19	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
20	Partially correct	4 ms	3788 KB	First line is correct, but the reconstruction is not properly formatted.
21	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
22	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
23	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
24	Partially correct	4 ms	3788 KB	First line is correct, but the reconstruction is not properly formatted.
25	Partially correct	4 ms	3788 KB	First line is correct, but the reconstruction is not properly formatted.
26	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.

Subtask #3
30.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
2	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
3	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
4	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
5	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
6	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
7	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
8	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
9	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
10	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
11	Partially correct	1 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
12	Partially correct	1 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
13	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
14	Partially correct	1 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
15	Partially correct	1 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
16	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
17	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
18	Partially correct	1 ms	336 KB	First line is correct, but the reconstruction is not properly formatted.
19	Partially correct	1 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
20	Partially correct	1 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
21	Partially correct	0 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
22	Partially correct	1 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
23	Partially correct	1 ms	332 KB	First line is correct, but the reconstruction is not properly formatted.
24	Partially correct	3 ms	2892 KB	First line is correct, but the reconstruction is not properly formatted.
25	Partially correct	1 ms	1484 KB	First line is correct, but the reconstruction is not properly formatted.
26	Partially correct	2 ms	2636 KB	First line is correct, but the reconstruction is not properly formatted.
27	Partially correct	1 ms	1356 KB	First line is correct, but the reconstruction is not properly formatted.
28	Partially correct	1 ms	1356 KB	First line is correct, but the reconstruction is not properly formatted.
29	Partially correct	1 ms	972 KB	First line is correct, but the reconstruction is not properly formatted.
30	Partially correct	1 ms	844 KB	First line is correct, but the reconstruction is not properly formatted.
31	Partially correct	2 ms	1616 KB	First line is correct, but the reconstruction is not properly formatted.
32	Partially correct	3 ms	3660 KB	First line is correct, but the reconstruction is not properly formatted.
33	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
34	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
35	Partially correct	4 ms	3788 KB	First line is correct, but the reconstruction is not properly formatted.
36	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
37	Partially correct	4 ms	3980 KB	First line is correct, but the reconstruction is not properly formatted.
38	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
39	Partially correct	4 ms	3952 KB	First line is correct, but the reconstruction is not properly formatted.
40	Partially correct	4 ms	3788 KB	First line is correct, but the reconstruction is not properly formatted.
41	Partially correct	4 ms	3788 KB	First line is correct, but the reconstruction is not properly formatted.
42	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
43	Partially correct	4 ms	3788 KB	First line is correct, but the reconstruction is not properly formatted.
44	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
45	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
46	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
47	Partially correct	4 ms	3788 KB	First line is correct, but the reconstruction is not properly formatted.
48	Partially correct	4 ms	3788 KB	First line is correct, but the reconstruction is not properly formatted.
49	Partially correct	4 ms	3916 KB	First line is correct, but the reconstruction is not properly formatted.
50	Partially correct	170 ms	29948 KB	First line is correct, but the reconstruction is not properly formatted.
51	Partially correct	630 ms	22724 KB	First line is correct, but the reconstruction is not properly formatted.
52	Partially correct	310 ms	32096 KB	First line is correct, but the reconstruction is not properly formatted.
53	Partially correct	172 ms	30748 KB	First line is correct, but the reconstruction is not properly formatted.
54	Partially correct	212 ms	26728 KB	First line is correct, but the reconstruction is not properly formatted.
55	Partially correct	217 ms	32828 KB	First line is correct, but the reconstruction is not properly formatted.
56	Partially correct	197 ms	33256 KB	First line is correct, but the reconstruction is not properly formatted.
57	Partially correct	185 ms	32396 KB	First line is correct, but the reconstruction is not properly formatted.
58	Partially correct	754 ms	22696 KB	First line is correct, but the reconstruction is not properly formatted.
59	Partially correct	198 ms	27492 KB	First line is correct, but the reconstruction is not properly formatted.
60	Partially correct	221 ms	31204 KB	First line is correct, but the reconstruction is not properly formatted.
61	Partially correct	246 ms	26384 KB	First line is correct, but the reconstruction is not properly formatted.
62	Partially correct	221 ms	31156 KB	First line is correct, but the reconstruction is not properly formatted.
63	Partially correct	216 ms	31732 KB	First line is correct, but the reconstruction is not properly formatted.
64	Partially correct	160 ms	23220 KB	First line is correct, but the reconstruction is not properly formatted.
65	Partially correct	182 ms	31504 KB	First line is correct, but the reconstruction is not properly formatted.
66	Partially correct	243 ms	28032 KB	First line is correct, but the reconstruction is not properly formatted.
67	Partially correct	304 ms	30344 KB	First line is correct, but the reconstruction is not properly formatted.
68	Partially correct	248 ms	32768 KB	First line is correct, but the reconstruction is not properly formatted.
69	Partially correct	220 ms	29964 KB	First line is correct, but the reconstruction is not properly formatted.
70	Partially correct	205 ms	30784 KB	First line is correct, but the reconstruction is not properly formatted.
71	Partially correct	341 ms	33288 KB	First line is correct, but the reconstruction is not properly formatted.
72	Partially correct	244 ms	34824 KB	First line is correct, but the reconstruction is not properly formatted.
73	Partially correct	277 ms	34112 KB	First line is correct, but the reconstruction is not properly formatted.
74	Partially correct	332 ms	33496 KB	First line is correct, but the reconstruction is not properly formatted.
75	Partially correct	273 ms	34400 KB	First line is correct, but the reconstruction is not properly formatted.

답안 #388184

Compilation message

Subtask #1 9.0 / 18.0

Subtask #2 16.0 / 32.0

Subtask #3 30.0 / 60.0

Subtask #1
9.0 / 18.0

Subtask #2
16.0 / 32.0

Subtask #3
30.0 / 60.0