oj.uz

Submission #330168

# Submission time Handle Problem Language Result Execution time Memory
330168 2020-11-24T05:09:26 Z Kevin_Zhang_TW Dango Maker (JOI18_dango_maker) C++17
13 / 100
 1 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template<class T> 
bool chmin(T &a, T b) { return b < a ? (a = b, true) : false; }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U>
void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T>
void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 3005;
char w[MAX_N][MAX_N];
int n, m, a, b, id[MAX_N][MAX_N];
bool valid (char a, char b, char c) { return a == 'R' && b == 'G' && c == 'W'; }
struct dsu {
	vector<int> g, sz;
	dsu(int n) {
		g.resize(n), sz.resize(n, 1);
		iota(AI(g), 0);
	}
	int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); }
	bool merge(int a, int b) {
		a = F(a), b = F(b);
		if (a == b) return false;
		if (sz[a] < sz[b]) swap(a, b);
		return sz[a] += sz[b], g[b] = a, true;
	} 
	int operator()(int i) { return F(i) ; }
};

int solve() {
	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= m;++j) { 
			if (valid(w[i][j-1], w[i][j], w[i][j+1])) 
				id[i][j] = ++b; 
		}
	vector<pair<int,int>> alle;

	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= m;++j) { 
			if (valid(w[i-1][j], w[i][j], w[i+1][j])) {
				++a;
				if (id[i-1][j+1]) 
					alle.pb(a, id[i-1][j+1]);
				if (id[i][j])
					alle.pb(a, id[i][j]);
				if (id[i+1][j-1])
					alle.pb(a, id[i+1][j-1]);
			} 
		}

	for (auto &[x, y] : alle)
		y += a; 
	DE(a, b);

	b += a;
	
	dsu D(b * 2 + 10);
	vector<int> cnt(b * 2 + 10);

	for (auto [x, y] : alle)
		D.merge(x, y + b), D.merge(x + b, y);
	int res = 0;

	for (int i = 1;i <= b;++i)
		++cnt[ D(i) ];
	for (int i = 1;i <= b;++i) {
		res += max(cnt[D(i)], cnt[D(i+b)]);

		assert(D(i) != D(i+b));
		//DE(D(i), D(i+b)); 
		cnt[D(i)] = cnt[D(i+b)] = 0;
	} 
	assert(res <= b);
	return res;
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 1;i <= n;++i)
		cin >> w[i] + 1;
	cout << solve() << '\n';
}

Compilation message

dango_maker.cpp: In function 'int solve()':
dango_maker.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 | #define DE(...) 0
      |                 ^
dango_maker.cpp:65:2: note: in expansion of macro 'DE'
   65 |  DE(a, b);
      |  ^~
dango_maker.cpp: In function 'int32_t main()':
dango_maker.cpp:92:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |   cin >> w[i] + 1;
      |          ~~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 376 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 1 ms 364 KB Output is correct
33 Correct 1 ms 364 KB Output is correct
34 Incorrect 1 ms 364 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 376 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 1 ms 364 KB Output is correct
33 Correct 1 ms 364 KB Output is correct
34 Incorrect 1 ms 364 KB Output isn't correct
35 Halted 0 ms 0 KB -