# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
530618 | 2022-02-26T03:14:10 Z | kevin | Dango Maker (JOI18_dango_maker) | C++17 | 124 ms | 211984 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long #define nl cout<<"\n" #define all(x) x.begin(), x.end() #define f first #define s second #define ca(v) for(auto i:v) cout<<i<<" "; const int MOD = 1e9 + 7; int onv[3001][3001]; int onh[3001][3001]; list<int> adj[3001*3001]; bool vis[3001*3001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); if (fopen("input.in", "r")) freopen("input.in", "r", stdin); int n, m; cin>>n>>m; char grid[n][m]; for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ cin>>grid[i][j]; } } int cnt = 0; for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ if(grid[i][j] == 'R' && j+2 < m && grid[i][j+1] == 'G' && grid[i][j+2] == 'W') onh[i][j] = ++cnt; } } for(int j=0; j<m; j++){ for(int i=0; i<n; i++){ if(grid[i][j] == 'R' && i+2 < n && grid[i+1][j] == 'G' && grid[i+2][j] == 'W') onv[i][j] = ++cnt; } } for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ if(onh[i][j]){ for(int k=0; k<3; k++){ if(i-k >= 0 && j+k < m && onv[i-k][j+k]){ adj[onh[i][j]].push_back(onv[i-k][j+k]); adj[onv[i-k][j+k]].push_back(onh[i][j]); } } } } } int ans = 0; vector<int> label(cnt+1, 0); for(int i=1; i<=cnt; i++){ if(!vis[i]){ vis[i] = 1; int cn[2] = {0, 0}; queue<pair<int, int>> q; q.push({i, 0}); while(q.size()){ auto c = q.front(); cn[c.s]++; q.pop(); for(int a:adj[c.f]){ if(!vis[a]){ label[a] = 1-c.s; q.push({a, 1-c.s}); vis[a] = 1; } else assert(label[a] == 1-c.s); } } ans += max(cn[0], cn[1]); } } cout<<ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 95 ms | 211780 KB | Output is correct |
2 | Correct | 95 ms | 211784 KB | Output is correct |
3 | Correct | 98 ms | 211788 KB | Output is correct |
4 | Correct | 122 ms | 211792 KB | Output is correct |
5 | Correct | 121 ms | 211752 KB | Output is correct |
6 | Correct | 92 ms | 211780 KB | Output is correct |
7 | Correct | 93 ms | 211784 KB | Output is correct |
8 | Correct | 95 ms | 211768 KB | Output is correct |
9 | Correct | 111 ms | 211752 KB | Output is correct |
10 | Correct | 93 ms | 211792 KB | Output is correct |
11 | Correct | 93 ms | 211772 KB | Output is correct |
12 | Correct | 94 ms | 211756 KB | Output is correct |
13 | Correct | 95 ms | 211752 KB | Output is correct |
14 | Correct | 94 ms | 211772 KB | Output is correct |
15 | Correct | 111 ms | 211840 KB | Output is correct |
16 | Correct | 100 ms | 211964 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 95 ms | 211780 KB | Output is correct |
2 | Correct | 95 ms | 211784 KB | Output is correct |
3 | Correct | 98 ms | 211788 KB | Output is correct |
4 | Correct | 122 ms | 211792 KB | Output is correct |
5 | Correct | 121 ms | 211752 KB | Output is correct |
6 | Correct | 92 ms | 211780 KB | Output is correct |
7 | Correct | 93 ms | 211784 KB | Output is correct |
8 | Correct | 95 ms | 211768 KB | Output is correct |
9 | Correct | 111 ms | 211752 KB | Output is correct |
10 | Correct | 93 ms | 211792 KB | Output is correct |
11 | Correct | 93 ms | 211772 KB | Output is correct |
12 | Correct | 94 ms | 211756 KB | Output is correct |
13 | Correct | 95 ms | 211752 KB | Output is correct |
14 | Correct | 94 ms | 211772 KB | Output is correct |
15 | Correct | 111 ms | 211840 KB | Output is correct |
16 | Correct | 100 ms | 211964 KB | Output is correct |
17 | Correct | 95 ms | 211804 KB | Output is correct |
18 | Correct | 94 ms | 211708 KB | Output is correct |
19 | Correct | 124 ms | 211736 KB | Output is correct |
20 | Correct | 93 ms | 211824 KB | Output is correct |
21 | Correct | 100 ms | 211728 KB | Output is correct |
22 | Correct | 95 ms | 211780 KB | Output is correct |
23 | Correct | 97 ms | 211776 KB | Output is correct |
24 | Correct | 93 ms | 211696 KB | Output is correct |
25 | Correct | 91 ms | 211780 KB | Output is correct |
26 | Correct | 103 ms | 211816 KB | Output is correct |
27 | Correct | 95 ms | 211780 KB | Output is correct |
28 | Correct | 94 ms | 211840 KB | Output is correct |
29 | Correct | 93 ms | 211768 KB | Output is correct |
30 | Correct | 94 ms | 211720 KB | Output is correct |
31 | Correct | 107 ms | 211764 KB | Output is correct |
32 | Correct | 95 ms | 211728 KB | Output is correct |
33 | Correct | 92 ms | 211860 KB | Output is correct |
34 | Incorrect | 96 ms | 211984 KB | Output isn't correct |
35 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 95 ms | 211780 KB | Output is correct |
2 | Correct | 95 ms | 211784 KB | Output is correct |
3 | Correct | 98 ms | 211788 KB | Output is correct |
4 | Correct | 122 ms | 211792 KB | Output is correct |
5 | Correct | 121 ms | 211752 KB | Output is correct |
6 | Correct | 92 ms | 211780 KB | Output is correct |
7 | Correct | 93 ms | 211784 KB | Output is correct |
8 | Correct | 95 ms | 211768 KB | Output is correct |
9 | Correct | 111 ms | 211752 KB | Output is correct |
10 | Correct | 93 ms | 211792 KB | Output is correct |
11 | Correct | 93 ms | 211772 KB | Output is correct |
12 | Correct | 94 ms | 211756 KB | Output is correct |
13 | Correct | 95 ms | 211752 KB | Output is correct |
14 | Correct | 94 ms | 211772 KB | Output is correct |
15 | Correct | 111 ms | 211840 KB | Output is correct |
16 | Correct | 100 ms | 211964 KB | Output is correct |
17 | Correct | 95 ms | 211804 KB | Output is correct |
18 | Correct | 94 ms | 211708 KB | Output is correct |
19 | Correct | 124 ms | 211736 KB | Output is correct |
20 | Correct | 93 ms | 211824 KB | Output is correct |
21 | Correct | 100 ms | 211728 KB | Output is correct |
22 | Correct | 95 ms | 211780 KB | Output is correct |
23 | Correct | 97 ms | 211776 KB | Output is correct |
24 | Correct | 93 ms | 211696 KB | Output is correct |
25 | Correct | 91 ms | 211780 KB | Output is correct |
26 | Correct | 103 ms | 211816 KB | Output is correct |
27 | Correct | 95 ms | 211780 KB | Output is correct |
28 | Correct | 94 ms | 211840 KB | Output is correct |
29 | Correct | 93 ms | 211768 KB | Output is correct |
30 | Correct | 94 ms | 211720 KB | Output is correct |
31 | Correct | 107 ms | 211764 KB | Output is correct |
32 | Correct | 95 ms | 211728 KB | Output is correct |
33 | Correct | 92 ms | 211860 KB | Output is correct |
34 | Incorrect | 96 ms | 211984 KB | Output isn't correct |
35 | Halted | 0 ms | 0 KB | - |