oj.uz

Submission #313014

# Submission time Handle Problem Language Result Execution time Memory
313014 2020-10-15T00:32:39 Z LucaDantas Dango Maker (JOI18_dango_maker) C++17
13 / 100
 1 ms 404 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[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

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);
      |                ~~~~~^~~~~~~~~~~

Subtask #1
13.0 / 13.0

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