oj.uz

Submission #366449

# Submission time Handle Problem Language Result Execution time Memory
366449 2021-02-14T08:18:03 Z Return_0 Skandi (COCI20_skandi) C++17
110 / 110
 195 ms 24936 KB 
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef int ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< x << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

cl inf = sizeof(ll) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
	return out << a.first << ' ' << a.second;    }
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	if(a.empty())return out<<"[]";out<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());)out<< ", " <<a[i];return out<<']';}
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 5e2 + 3;

ll n, m, X, ans, lft [N][N], mark [N * N * 2], ptr = 2, match [N * N * 2];
char a [N][N];
vector <ll> adj [N * N * 2], lewd;

inline ll conv (cl &x, cl &y) { return (x - 1) * m + y; }

void DFS (cl &v, cl &h = 0) {
	mark[v] = 1;
	if (h)	lewd.push_back(v);
	for (auto &u : adj[v]) if (!mark[u])	DFS(u, 1 - h);
}

bool dfs (ll v) {
    mark[v] = ptr;
    for (auto u : adj[v]) if (match[u] == -1 || (mark[match[u]] != ptr && dfs(match[u]))) {
        match[v] = u, match[u] = v;
        return true;
    }
    return false;
}

void Find_Matching () {
    memset(match, -1, sizeof match);
    memset(mark, -1, sizeof mark);
	bool can_find = true; ptr = -1;
    while (can_find) {
        can_find = false, ptr++;
        for (ll v = ptr; v < SZ(lewd); v++) if (mark[lewd[v]] != ptr && match[lewd[v]] == -1) can_find |= dfs(lewd[v]);
    }
}

void force (cl &v, cl &tp) {
	mark[v] = tp;
	if (tp == 1) {
		if (!mark[match[v]])	force(match[v], 2);
	}
	else for (auto &u : adj[v]) if (!mark[u]) force(u, 1);
}

inline pll decompose (ll v) {
	if (v > X)	v -= X;
	ll x, y = v % m ? v % m : m;
	x = (v - y) / m + 1;
	return pll(x, y);
}

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

	cin>> n >> m; X = n * m;
	for (ll i = 1; i <= n; i++)	for (ll j = 1; j <= m; j++)	cin>> a[i][j];
	for (ll i = 1, cur = -1; i <= n; i++) for (ll j = 1; j <= m; j++) {
		if (a[i][j] - '0')	cur = conv(i, j);
		else lft[i][j] = cur;
	}
	for (ll j = 1, cur = -1; j <= m; j++) for (ll i = 1; i <= n; i++) {
		if (a[i][j] - '0')	cur = conv(i, j) + X;
		else adj[lft[i][j]].push_back(cur), adj[cur].push_back(lft[i][j]);
	}

	for (ll v = 1; v <= X + X; v++)	if (!mark[v])	DFS(v);

	Find_Matching();

	memset(mark, 0, sizeof mark);
	for (ll v = 1; v <= X + X; v++) {
		if (match[v] < 1)	force(v, 2);
		else	ans++;
	}

	cout<< ans / 2 << '\n';
	for (ll v = 1; v <= X + X; v++) {
		if (match[v] > 0 && !mark[v])	mark[v] = 1, mark[match[v]] = 2;
		if (match[v] > 0 && mark[v] == 1) {
			if (v > X)	cout<< decompose(v) << " DOLJE\n";
			else	cout<< decompose(v) << " DESNO\n";
		}
	}

	return 0;
}
/*

*/

Compilation message

skandi.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)':
skandi.cpp:44:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   44 |  if(a.empty())return out<<"[]";out<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());)out<< ", " <<a[i];return out<<']';}
      |  ^~
skandi.cpp:44:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   44 |  if(a.empty())return out<<"[]";out<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());)out<< ", " <<a[i];return out<<']';}
      |                                ^~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16236 KB Correct.
2 Correct 14 ms 16236 KB Correct.
3 Correct 12 ms 16236 KB Correct.
4 Correct 11 ms 16236 KB Correct.
5 Correct 11 ms 16236 KB Correct.
6 Correct 11 ms 16384 KB Correct.
7 Correct 11 ms 16236 KB Correct.
8 Correct 11 ms 16236 KB Correct.
9 Correct 12 ms 16236 KB Correct.
10 Correct 11 ms 16236 KB Correct.
11 Correct 12 ms 16236 KB Correct.
12 Correct 11 ms 16236 KB Correct.
13 Correct 12 ms 16236 KB Correct.
14 Correct 12 ms 16384 KB Correct.
15 Correct 12 ms 16236 KB Correct.
16 Correct 11 ms 16236 KB Correct.
17 Correct 12 ms 16236 KB Correct.
18 Correct 11 ms 16236 KB Correct.
19 Correct 11 ms 16236 KB Correct.
20 Correct 12 ms 16236 KB Correct.
21 Correct 11 ms 16236 KB Correct.
22 Correct 11 ms 16236 KB Correct.
23 Correct 11 ms 16236 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17004 KB Correct.
2 Correct 14 ms 16620 KB Correct.
3 Correct 12 ms 17152 KB Correct.
4 Correct 12 ms 16620 KB Correct.
5 Correct 12 ms 16620 KB Correct.
6 Correct 12 ms 16364 KB Correct.
7 Correct 12 ms 16364 KB Correct.
8 Correct 13 ms 16620 KB Correct.
9 Correct 13 ms 17516 KB Correct.
10 Correct 13 ms 17772 KB Correct.
11 Correct 13 ms 17516 KB Correct.
12 Correct 13 ms 17516 KB Correct.
13 Correct 13 ms 17516 KB Correct.
14 Correct 14 ms 17516 KB Correct.
15 Correct 13 ms 17516 KB Correct.
16 Correct 13 ms 17644 KB Correct.
17 Correct 13 ms 17516 KB Correct.
18 Correct 13 ms 17516 KB Correct.
19 Correct 14 ms 17516 KB Correct.
20 Correct 13 ms 17516 KB Correct.
21 Correct 13 ms 17516 KB Correct.
22 Correct 13 ms 17516 KB Correct.
23 Correct 13 ms 17516 KB Correct.
24 Correct 13 ms 17516 KB Correct.
25 Correct 13 ms 17516 KB Correct.
26 Correct 13 ms 17536 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16236 KB Correct.
2 Correct 14 ms 16236 KB Correct.
3 Correct 12 ms 16236 KB Correct.
4 Correct 11 ms 16236 KB Correct.
5 Correct 11 ms 16236 KB Correct.
6 Correct 11 ms 16384 KB Correct.
7 Correct 11 ms 16236 KB Correct.
8 Correct 11 ms 16236 KB Correct.
9 Correct 12 ms 16236 KB Correct.
10 Correct 11 ms 16236 KB Correct.
11 Correct 12 ms 16236 KB Correct.
12 Correct 11 ms 16236 KB Correct.
13 Correct 12 ms 16236 KB Correct.
14 Correct 12 ms 16384 KB Correct.
15 Correct 12 ms 16236 KB Correct.
16 Correct 11 ms 16236 KB Correct.
17 Correct 12 ms 16236 KB Correct.
18 Correct 11 ms 16236 KB Correct.
19 Correct 11 ms 16236 KB Correct.
20 Correct 12 ms 16236 KB Correct.
21 Correct 11 ms 16236 KB Correct.
22 Correct 11 ms 16236 KB Correct.
23 Correct 11 ms 16236 KB Correct.
24 Correct 12 ms 17004 KB Correct.
25 Correct 14 ms 16620 KB Correct.
26 Correct 12 ms 17152 KB Correct.
27 Correct 12 ms 16620 KB Correct.
28 Correct 12 ms 16620 KB Correct.
29 Correct 12 ms 16364 KB Correct.
30 Correct 12 ms 16364 KB Correct.
31 Correct 13 ms 16620 KB Correct.
32 Correct 13 ms 17516 KB Correct.
33 Correct 13 ms 17772 KB Correct.
34 Correct 13 ms 17516 KB Correct.
35 Correct 13 ms 17516 KB Correct.
36 Correct 13 ms 17516 KB Correct.
37 Correct 14 ms 17516 KB Correct.
38 Correct 13 ms 17516 KB Correct.
39 Correct 13 ms 17644 KB Correct.
40 Correct 13 ms 17516 KB Correct.
41 Correct 13 ms 17516 KB Correct.
42 Correct 14 ms 17516 KB Correct.
43 Correct 13 ms 17516 KB Correct.
44 Correct 13 ms 17516 KB Correct.
45 Correct 13 ms 17516 KB Correct.
46 Correct 13 ms 17516 KB Correct.
47 Correct 13 ms 17516 KB Correct.
48 Correct 13 ms 17516 KB Correct.
49 Correct 13 ms 17536 KB Correct.
50 Correct 74 ms 21608 KB Correct.
51 Correct 164 ms 21868 KB Correct.
52 Correct 112 ms 24228 KB Correct.
53 Correct 88 ms 21740 KB Correct.
54 Correct 95 ms 23144 KB Correct.
55 Correct 97 ms 22376 KB Correct.
56 Correct 78 ms 21992 KB Correct.
57 Correct 88 ms 21872 KB Correct.
58 Correct 195 ms 21484 KB Correct.
59 Correct 77 ms 21480 KB Correct.
60 Correct 85 ms 21992 KB Correct.
61 Correct 103 ms 23912 KB Correct.
62 Correct 88 ms 21996 KB Correct.
63 Correct 83 ms 22124 KB Correct.
64 Correct 36 ms 19820 KB Correct.
65 Correct 88 ms 22120 KB Correct.
66 Correct 97 ms 23912 KB Correct.
67 Correct 121 ms 24936 KB Correct.
68 Correct 96 ms 22380 KB Correct.
69 Correct 86 ms 21864 KB Correct.
70 Correct 83 ms 21996 KB Correct.
71 Correct 116 ms 24432 KB Correct.
72 Correct 94 ms 22336 KB Correct.
73 Correct 108 ms 23016 KB Correct.
74 Correct 112 ms 24680 KB Correct.
75 Correct 116 ms 22768 KB Correct.