oj.uz

Submission #924642

# Submission time Handle Problem Language Result Execution time Memory
924642 2024-02-09T11:01:56 Z thinknoexit Dango Maker (JOI18_dango_maker) C++17
0 / 100
 29 ms 82716 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3000001;
int a[3030][3030];
int b[3030][3030];
char c[3030][3030];
int deg[N];
bool p[N], vis[N];
vector<int> adj[N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> c[i][j];
            if (i >= 3) {
                if (c[i][j] == 'W' && c[i - 1][j] == 'G' && c[i - 2][j] == 'R') {
                    cnt++;
                    a[i][j] = a[i - 1][j] = a[i - 2][j] = cnt;
                    p[cnt] = 0;
                }
            }
            if (j >= 3) {
                if (c[i][j] == 'W' && c[i][j - 1] == 'G' && c[i][j - 2] == 'R') {
                    cnt++;
                    b[i][j] = b[i][j - 1] = b[i][j - 2] = cnt;
                    p[cnt] = 1;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (a[i][j] && b[i][j]) {
                adj[a[i][j]].push_back(b[i][j]);
                adj[b[i][j]].push_back(a[i][j]);
                deg[a[i][j]]++;
                deg[b[i][j]]++;
            }
        }
    }
    for (int i = 1;i <= cnt;i++) {
        if (vis[i]) continue;
        int c1 = 0, c2 = 0;
        int d1 = 0, d2 = 0;
        queue<int> q;
        q.push(i);
        vis[i] = 1;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            if (p[v]) {
                c1++;
                if (deg[v] == 1) d1++;
            }
            else {
                c2++;
                if (deg[v] == 1) d2++;
            }
            int t1 = 0, t2 = 0;
            for (auto& x : adj[v]) {
                if (deg[x] == 1) {
                    if (p[x]) t1++;
                    else t2++;
                }
                if (vis[x]) continue;
                vis[x] = 1;
                q.push(x);
            }
            d1 = max(d1, t1), d2 = max(d2, t2);
        }
        int res = max(c1, c2);
        if (d1 >= 2) res = max(res, c2 + 1);
        if (d2 >= 2) res = max(res, c1 + 1);
        ans += res;
    }
    cout << ans;
    return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 74396 KB Output is correct
2 Correct 16 ms 74332 KB Output is correct
3 Correct 16 ms 74516 KB Output is correct
4 Correct 16 ms 74392 KB Output is correct
5 Correct 16 ms 74364 KB Output is correct
6 Incorrect 20 ms 82716 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 74396 KB Output is correct
2 Correct 16 ms 74332 KB Output is correct
3 Correct 16 ms 74516 KB Output is correct
4 Correct 16 ms 74392 KB Output is correct
5 Correct 16 ms 74364 KB Output is correct
6 Incorrect 20 ms 82716 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 74396 KB Output is correct
2 Correct 16 ms 74332 KB Output is correct
3 Correct 16 ms 74516 KB Output is correct
4 Correct 16 ms 74392 KB Output is correct
5 Correct 16 ms 74364 KB Output is correct
6 Incorrect 20 ms 82716 KB Output isn't correct
7 Halted 0 ms 0 KB -