Submission #312918

#	Time	Username	Problem	Language	Result	Execution time	Memory
312918		LucaDantas	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	1 ms	392 KiB

dango_maker

#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 (stderr)

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 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67