oj.uz

Submission #680463

# Submission time Handle Problem Language Result Execution time Memory
680463 2023-01-10T22:59:02 Z Neos Dango Maker (JOI18_dango_maker) C++14
0 / 100
 16 ms 28792 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define getBit(x, i) ((x) >> (i) & 1)
#define rep(i, begin, end) for (ll i = (begin); i <= (end); i++)
#define rrep(i, begin, end) for (ll i = (begin); i >= (end); i--)

typedef long long ll;
typedef pair<int, int> ii;

template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}

const int N = 3e3 + 7, M = 1e6 + 7, oo = 2e9;

int n, m, tot, cnt, match[M], mark[N][N];
string a[N];
bool vis[M];
vector<int> adj[M];

int g(int x, int y) {
    if (mark[x][y]) return mark[x][y];
    return mark[x][y] = ++cnt;
}

int mcbm(int u) {
    if (vis[u]) return 0;
    vis[u] = 1;
    for (int v: adj[u]) {
        if (match[v] == -1 || mcbm(match[v])) {
            match[v] = u;
            return 1;
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    rep(i, 1, n) cin >> a[i], a[i] = ' ' + a[i];
    rep(i, 1, n) rep(j, 1, m) {
        if (j + 2 <= m) tot += (a[i].substr(j, 3) == "RGW");
        if (i + 2 <= n) tot += (a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W');
        // (i, j) right | (j, i) down
        if (j + 2 <= m && j + 2 <= n) {
            if (a[i].substr(j, 3) == "RGW" && a[j][i] == 'R' && a[j + 1][i] == 'G' && a[j + 2][i] == 'W') {
                adj[g(i, j)].pb(g(j, i));
                adj[g(j, i)].pb(g(i, j));
            }
        }

        // (i, j) down | (j, i) right
        if (j <= n && i + 2 <= m && i + 2 <= n) {
            if (a[j].substr(i, 3) == "RGW" && a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W') {
                adj[g(i, j)].pb(g(j, i));
                adj[g(j, i)].pb(g(i, j));
            }
        }
    }

    int cnt = 0;
    memset(match, -1, sizeof match);
    rep(i, 1, tot) {
        memset(vis, 0, sizeof vis);
        cnt += mcbm(i);
    }
    cout << tot - cnt;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27732 KB Output is correct
2 Correct 13 ms 27780 KB Output is correct
3 Correct 13 ms 27764 KB Output is correct
4 Correct 13 ms 27732 KB Output is correct
5 Correct 16 ms 27792 KB Output is correct
6 Incorrect 14 ms 28792 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27732 KB Output is correct
2 Correct 13 ms 27780 KB Output is correct
3 Correct 13 ms 27764 KB Output is correct
4 Correct 13 ms 27732 KB Output is correct
5 Correct 16 ms 27792 KB Output is correct
6 Incorrect 14 ms 28792 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27732 KB Output is correct
2 Correct 13 ms 27780 KB Output is correct
3 Correct 13 ms 27764 KB Output is correct
4 Correct 13 ms 27732 KB Output is correct
5 Correct 16 ms 27792 KB Output is correct
6 Incorrect 14 ms 28792 KB Output isn't correct
7 Halted 0 ms 0 KB -