oj.uz

Submission #898373

# Submission time Handle Problem Language Result Execution time Memory
898373 2024-01-04T14:43:59 Z penguin133 Dango Maker (JOI18_dango_maker) C++17
13 / 100
 1 ms 4704 KB 
#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int par[9000005], hor[9000005], vert[9000005], used[9000005], n, m;
char A[3005][3005];

int getr(int x){return par[x] == x ? x : par[x] = getr(par[x]);}
void merge(int a, int b){
	a = getr(a), b = getr(b);
	if(a == b)return;
	par[b] = a;
	hor[a] += hor[b];
	vert[a] += vert[b];
}
inline int conv(int x, int y){
	return (x - 1) * m + y;
}

void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin >> A[i][j];
	for(int i = 1; i <= n * m; i++)par[i] = i;
	for(int i = 1; i <= n - 2; i++){
		for(int j = 1; j <= m; j++){
			if(A[i][j] == 'R' && A[i + 1][j] == 'G' && A[i + 2][j] == 'W'){
				merge(conv(i, j), conv(i + 1, j));
				merge(conv(i + 1, j), conv(i + 2, j));
				vert[getr(conv(i, j))]++;
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m - 2; j++){
			if(A[i][j] == 'R' && A[i][j + 1] == 'G' && A[i][j + 2] == 'W'){
				merge(conv(i, j), conv(i, j + 1));
				merge(conv(i, j + 1), conv(i, j + 2));
				hor[getr(conv(i, j))]++;
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= n * m; i++){
		if(used[getr(i)])continue;
		used[getr(i)] = 1;
		ans += max(hor[getr(i)], vert[getr(i)]);
	}
	cout << ans;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

dango_maker.cpp:60:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   60 | main(){
      | ^~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
0 / 20.0

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