oj.uz

Submission #388184

# Submission time Handle Problem Language Result Execution time Memory
388184 2021-04-10T12:33:11 Z BorisBarca Skandi (COCI20_skandi) C++14
55 / 110
 754 ms 34824 KB 
/*
$$$$$$$\                      $$\           $$$$$$$\
$$  __$$\                     \__|          $$  __$$\
$$ |  $$ | $$$$$$\   $$$$$$\  $$\  $$$$$$$\ $$ |  $$ | $$$$$$\   $$$$$$\   $$$$$$$\ $$$$$$\
$$$$$$$\ |$$  __$$\ $$  __$$\ $$ |$$  _____|$$$$$$$\ | \____$$\ $$  __$$\ $$  _____|\____$$\
$$  __$$\ $$ /  $$ |$$ |  \__|$$ |\$$$$$$\  $$  __$$\  $$$$$$$ |$$ |  \__|$$ /      $$$$$$$ |
$$ |  $$ |$$ |  $$ |$$ |      $$ | \____$$\ $$ |  $$ |$$  __$$ |$$ |      $$ |     $$  __$$ |
$$$$$$$  |\$$$$$$  |$$ |      $$ |$$$$$$$  |$$$$$$$  |\$$$$$$$ |$$ |      \$$$$$$$\\$$$$$$$ |
\_______/  \______/ \__|      \__|\_______/ \_______/  \_______|\__|       \_______|\_______|
*/
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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.