# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
770255 | 2023-07-01T03:43:51 Z | gun_gan | Dango Maker (JOI18_dango_maker) | C++17 | 120 ms | 247904 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MX = 3005; int N, M; char c[MX][MX]; int h[MX][MX], v[MX][MX]; vector<int> g[MX * MX]; int col[MX * MX]; int w = 0, b = 0; void dfs(int v) { if(col[v]) b++; else w++; for(auto u : g[v]) { if(col[u] == 2) { col[u] = col[v] ^ 1; dfs(u); } else { assert(col[u] == col[v] ^ 1); } } } int main() { cin.tie(0); ios_base::sync_with_stdio(0); for(int i = 0; i < MX * MX; i++) col[i] = 2; cin >> N >> M; for(int i = 0; i < N; i++) { for(int j = 0; j < M; j++) { cin >> c[i][j]; } } // build hori int cnt = 0; for(int i = 0; i < N; i++) { for(int j = 0; j + 2 < M; j++) { if(c[i][j] == 'R' && c[i][j + 1] == 'G' && c[i][j + 2] == 'W') { cnt++; h[i][j] = h[i][j + 1] = h[i][j + 2] = cnt; } } } // build vert for(int j = 0; j < M; j++) { for(int i = 0; i + 2 < N; i++) { if(c[i][j] == 'R' && c[i + 1][j] == 'G' && c[i + 2][j] == 'W') { cnt++; v[i][j] = v[i + 1][j] = v[i + 2][j] = cnt; } } } for(int i = 0; i < N; i++) { for(int j = 0; j < M; j++) { if(h[i][j] && v[i][j]) { g[h[i][j]].push_back(v[i][j]); g[v[i][j]].push_back(h[i][j]); } } } // traverse graph int ans = 0; for(int i = 1; i <= cnt; i++) { if(col[i] == 2) { col[i] = 0; w = 0, b = 0; dfs(i); ans += max(w, b); } } cout << ans << '\n'; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 113 ms | 247716 KB | Output is correct |
2 | Correct | 105 ms | 247680 KB | Output is correct |
3 | Correct | 102 ms | 247680 KB | Output is correct |
4 | Correct | 104 ms | 247628 KB | Output is correct |
5 | Correct | 102 ms | 247728 KB | Output is correct |
6 | Correct | 101 ms | 247672 KB | Output is correct |
7 | Correct | 111 ms | 247720 KB | Output is correct |
8 | Correct | 104 ms | 247732 KB | Output is correct |
9 | Correct | 102 ms | 247704 KB | Output is correct |
10 | Correct | 108 ms | 247740 KB | Output is correct |
11 | Correct | 110 ms | 247724 KB | Output is correct |
12 | Correct | 102 ms | 247652 KB | Output is correct |
13 | Correct | 103 ms | 247740 KB | Output is correct |
14 | Correct | 114 ms | 247700 KB | Output is correct |
15 | Correct | 105 ms | 247824 KB | Output is correct |
16 | Correct | 113 ms | 247724 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 113 ms | 247716 KB | Output is correct |
2 | Correct | 105 ms | 247680 KB | Output is correct |
3 | Correct | 102 ms | 247680 KB | Output is correct |
4 | Correct | 104 ms | 247628 KB | Output is correct |
5 | Correct | 102 ms | 247728 KB | Output is correct |
6 | Correct | 101 ms | 247672 KB | Output is correct |
7 | Correct | 111 ms | 247720 KB | Output is correct |
8 | Correct | 104 ms | 247732 KB | Output is correct |
9 | Correct | 102 ms | 247704 KB | Output is correct |
10 | Correct | 108 ms | 247740 KB | Output is correct |
11 | Correct | 110 ms | 247724 KB | Output is correct |
12 | Correct | 102 ms | 247652 KB | Output is correct |
13 | Correct | 103 ms | 247740 KB | Output is correct |
14 | Correct | 114 ms | 247700 KB | Output is correct |
15 | Correct | 105 ms | 247824 KB | Output is correct |
16 | Correct | 113 ms | 247724 KB | Output is correct |
17 | Correct | 102 ms | 247716 KB | Output is correct |
18 | Correct | 110 ms | 247692 KB | Output is correct |
19 | Correct | 102 ms | 247720 KB | Output is correct |
20 | Correct | 103 ms | 247688 KB | Output is correct |
21 | Correct | 102 ms | 247700 KB | Output is correct |
22 | Correct | 104 ms | 247792 KB | Output is correct |
23 | Correct | 102 ms | 247692 KB | Output is correct |
24 | Correct | 103 ms | 247668 KB | Output is correct |
25 | Correct | 102 ms | 247628 KB | Output is correct |
26 | Correct | 104 ms | 247692 KB | Output is correct |
27 | Correct | 102 ms | 247776 KB | Output is correct |
28 | Correct | 103 ms | 247756 KB | Output is correct |
29 | Correct | 104 ms | 247744 KB | Output is correct |
30 | Correct | 104 ms | 247692 KB | Output is correct |
31 | Correct | 120 ms | 247748 KB | Output is correct |
32 | Correct | 103 ms | 247732 KB | Output is correct |
33 | Correct | 106 ms | 247904 KB | Output is correct |
34 | Incorrect | 106 ms | 247768 KB | Output isn't correct |
35 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 113 ms | 247716 KB | Output is correct |
2 | Correct | 105 ms | 247680 KB | Output is correct |
3 | Correct | 102 ms | 247680 KB | Output is correct |
4 | Correct | 104 ms | 247628 KB | Output is correct |
5 | Correct | 102 ms | 247728 KB | Output is correct |
6 | Correct | 101 ms | 247672 KB | Output is correct |
7 | Correct | 111 ms | 247720 KB | Output is correct |
8 | Correct | 104 ms | 247732 KB | Output is correct |
9 | Correct | 102 ms | 247704 KB | Output is correct |
10 | Correct | 108 ms | 247740 KB | Output is correct |
11 | Correct | 110 ms | 247724 KB | Output is correct |
12 | Correct | 102 ms | 247652 KB | Output is correct |
13 | Correct | 103 ms | 247740 KB | Output is correct |
14 | Correct | 114 ms | 247700 KB | Output is correct |
15 | Correct | 105 ms | 247824 KB | Output is correct |
16 | Correct | 113 ms | 247724 KB | Output is correct |
17 | Correct | 102 ms | 247716 KB | Output is correct |
18 | Correct | 110 ms | 247692 KB | Output is correct |
19 | Correct | 102 ms | 247720 KB | Output is correct |
20 | Correct | 103 ms | 247688 KB | Output is correct |
21 | Correct | 102 ms | 247700 KB | Output is correct |
22 | Correct | 104 ms | 247792 KB | Output is correct |
23 | Correct | 102 ms | 247692 KB | Output is correct |
24 | Correct | 103 ms | 247668 KB | Output is correct |
25 | Correct | 102 ms | 247628 KB | Output is correct |
26 | Correct | 104 ms | 247692 KB | Output is correct |
27 | Correct | 102 ms | 247776 KB | Output is correct |
28 | Correct | 103 ms | 247756 KB | Output is correct |
29 | Correct | 104 ms | 247744 KB | Output is correct |
30 | Correct | 104 ms | 247692 KB | Output is correct |
31 | Correct | 120 ms | 247748 KB | Output is correct |
32 | Correct | 103 ms | 247732 KB | Output is correct |
33 | Correct | 106 ms | 247904 KB | Output is correct |
34 | Incorrect | 106 ms | 247768 KB | Output isn't correct |
35 | Halted | 0 ms | 0 KB | - |