oj.uz

Submission #312918

# Submission time Handle Problem Language Result Execution time Memory
312918 2020-10-14T16:45:11 Z LucaDantas Dango Maker (JOI18_dango_maker) C++17
13 / 100
 1 ms 392 KB 
#include<bits/stdc++.h>
using namespace std;

constexpr int maxn = 3e3+10;

int grid[maxn][maxn], n, m;

inline int pos(int i, int j) { return m*i+j; }

struct DSU
{
	int pai[maxn], peso[maxn], hor[maxn], ver[maxn];
	DSU() {for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1;}
	int find(int x) { return pai[x]==x?x:pai[x]=find(pai[x]); }
	void merge(int i, int j, int s) {
		if(s) {
			hor[pos(i,j)]++;
			join(pos(i, j), pos(i, j-1));
			join(pos(i, j), pos(i, j-2));
		}
		else {
			ver[pos(i,j)]++;
			join(pos(i, j), pos(i-1, j));
			join(pos(i, j), pos(i-2, j));
		}
	}
	void join(int a, int b) {
		a = find(a), b = find(b);
		if(a == b) return;
		if(peso[a] < peso[b])
			swap(a, b);
		pai[b] = a;
		peso[a] += b;
		hor[a] += hor[b];
		ver[a] += ver[b];
	}
} dsu;

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			char c; scanf(" %c", &c);
			grid[i][j] = (c=='R'?0:c=='G'?1:2);
		}
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(i >= 2 && grid[i][j] == 2 && grid[i-1][j] == 1 && grid[i-2][j] == 0)
				dsu.merge(i, j, 0);
			if(j >= 2 && grid[i][j] == 2 && grid[i][j-1] == 1 && grid[i][j-2] == 0)
				dsu.merge(i, j, 1);
		}
	}
	int ans = 0;
	for(int i = 0; i < n*m; i++) {
		if(dsu.find(i) == i)
			ans += max(dsu.hor[i], dsu.ver[i]);
	}
	printf("%d\n", ans);
}

Compilation message

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
dango_maker.cpp:43:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |    char c; scanf(" %c", &c);
      |            ~~~~~^~~~~~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 392 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Incorrect 1 ms 384 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 392 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Incorrect 1 ms 384 KB Output isn't correct
21 Halted 0 ms 0 KB -