oj.uz

Submission #712320

# Submission time Handle Problem Language Result Execution time Memory
712320 2023-03-18T14:45:49 Z dozer Dango Maker (JOI18_dango_maker) C++14
13 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n";
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 3005

const int modulo = 1e9 + 7;

int arr[N][N], root[N * N], done[N][N];
pii sz[N];
set<int> roots;

int find(int node)
{
	if (root[node] == node) return node;
	return root[node] = find(root[node]); 
}


void uni(int a, int b)
{
	a = find(a), b = find(b);
	if (sz[a].st + sz[a].nd < sz[b].st + sz[b].nd) swap(a, b);
	if (a == b) return;
	root[b] = a;
	roots.erase(b);
	sz[a].st += sz[b].st, sz[a].nd += sz[b].nd;
}

int32_t main()
{
	fastio();

	map<char, int> val;
	val['R'] = 1, val['G'] = 2, val['W'] = 3;

	int n, m;
	cin>>n>>m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			char tmp;
			cin>>tmp;
			arr[i][j] = val[tmp];
		}
	}
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) done[i][j] = (i - 1) * m + j;
	for (int i = 1; i <= n * m; i++) root[i] = i, roots.insert(i);

	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			int val = 0, f = 1;
			for (int k = i; k <= i + 2; k++)
			{
				val += arr[k][j] * f;
				f *= 10;
			}
			if (val == 321)
			{
				//cout<<"v "<<i<<sp<<j<<endl;
				sz[find(done[i][j])].st++;
				for (int k = i + 1; k <= i + 2; k++)
					uni(done[i][j], done[k][j]);
			}


			val = 0, f = 1;
			for (int k = j; k <= j + 2; k++)
			{
				val += arr[i][k] * f;
				f *= 10;
			}
			if (val == 321)
			{
				//cout<<"> "<<i<<sp<<j<<endl;
				sz[find(done[i][j])].nd++;
				for (int k = j + 1; k <= j + 2; k++)
					uni(done[i][j], done[i][k]);
			}
		}
	}

	for (auto i : roots)
	{
		ans += max(sz[i].st, sz[i].nd);
	}
	cout<<ans<<endl;
	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\n";
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 328 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 328 KB Output is correct
34 Incorrect 1 ms 324 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 328 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 328 KB Output is correct
34 Incorrect 1 ms 324 KB Output isn't correct
35 Halted 0 ms 0 KB -