Submission #313014

#TimeUsernameProblemLanguageResultExecution timeMemory
313014LucaDantasDango Maker (JOI18_dango_maker)C++17
13 / 100
1 ms404 KiB
    #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[find(pos(i,j))]++;
    			join(pos(i, j), pos(i, j-1));
    			join(pos(i, j), pos(i, j-2));
    		}
    		else {
    			ver[find(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:11: 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:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |        char c; scanf(" %c", &c);
      |                ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...