oj.uz

Submission #680464

# Submission time Handle Problem Language Result Execution time Memory
680464 2023-01-10T23:08:42 Z Neos Dango Maker (JOI18_dango_maker) C++14
0 / 100
 17 ms 28804 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, sz, 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] = ++sz;
}

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');
    }
    rep(i, 1, n) rep(j, i, m) {
        // (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));
            }
        }

        // (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));
            }
        }
    }

    int cnt = 0;
    memset(match, -1, sizeof match);
    rep(i, 1, sz) {
        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 27776 KB Output is correct
2 Correct 17 ms 27704 KB Output is correct
3 Correct 16 ms 27720 KB Output is correct
4 Correct 14 ms 27732 KB Output is correct
5 Correct 16 ms 27824 KB Output is correct
6 Correct 14 ms 28756 KB Output is correct
7 Correct 14 ms 28756 KB Output is correct
8 Correct 13 ms 28776 KB Output is correct
9 Correct 15 ms 28804 KB Output is correct
10 Correct 14 ms 27720 KB Output is correct
11 Correct 14 ms 28756 KB Output is correct
12 Correct 14 ms 28780 KB Output is correct
13 Incorrect 12 ms 27808 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27776 KB Output is correct
2 Correct 17 ms 27704 KB Output is correct
3 Correct 16 ms 27720 KB Output is correct
4 Correct 14 ms 27732 KB Output is correct
5 Correct 16 ms 27824 KB Output is correct
6 Correct 14 ms 28756 KB Output is correct
7 Correct 14 ms 28756 KB Output is correct
8 Correct 13 ms 28776 KB Output is correct
9 Correct 15 ms 28804 KB Output is correct
10 Correct 14 ms 27720 KB Output is correct
11 Correct 14 ms 28756 KB Output is correct
12 Correct 14 ms 28780 KB Output is correct
13 Incorrect 12 ms 27808 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27776 KB Output is correct
2 Correct 17 ms 27704 KB Output is correct
3 Correct 16 ms 27720 KB Output is correct
4 Correct 14 ms 27732 KB Output is correct
5 Correct 16 ms 27824 KB Output is correct
6 Correct 14 ms 28756 KB Output is correct
7 Correct 14 ms 28756 KB Output is correct
8 Correct 13 ms 28776 KB Output is correct
9 Correct 15 ms 28804 KB Output is correct
10 Correct 14 ms 27720 KB Output is correct
11 Correct 14 ms 28756 KB Output is correct
12 Correct 14 ms 28780 KB Output is correct
13 Incorrect 12 ms 27808 KB Output isn't correct
14 Halted 0 ms 0 KB -