Submission #680346

#	Time	Username	Problem	Language	Result	Execution time	Memory
680346		vjudge1	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	2084 ms	1116 KiB

dango_maker

#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 = 4e2 + 7, M = 20, oo = 2e9;

int n, m, s, t, res;
int tr[N], c[N][N], f[N][N];
bool st[N], en[N], mid[N], vis[N];
vector<int> adj[N];
string a[N];

bool bfs() {
    queue<int> q; q.push(s);
    memset(tr, 0, sizeof tr);
    memset(vis, 0, sizeof vis);
    tr[s] = -1; vis[s] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == t) return 1;

        rep(v, 0, t) {
            if (!vis[v] && c[u][v] > f[u][v]) {
                tr[v] = u; vis[v] = 1;
                q.push(v);
            }
        }
    }
    return 0;
}

void incflow() {
    int v = t, dif = oo;
    for (; tr[v] != -1; v = tr[v]) {
        int u = tr[v];
        dif = min(dif, c[u][v] - f[u][v]);
    }

    v = t; res += dif;
    for (; tr[v] != -1; v = tr[v]) {
        int u = tr[v];
        f[u][v] += dif;
        f[v][u] -= dif;
    }
}

int g(int x, int y) {
    return (x - 1) * m + y;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> m;
    rep(i, 1, n) cin >> a[i], a[i] = ' ' + a[i];
    rep(i, 1, n) rep(j, 1, m) {
        // go right
        if (j + 2 <= m && a[i].substr(j, 3) == "RGW") {
            int fi = g(i, j), se = g(i, j + 1), th = g(i, j + 2);
            adj[fi].pb(se); adj[se].pb(th);

            c[fi][se] = c[se][fi] = 1;
            c[se][th] = c[th][se] = 1;

            st[fi] = en[th] = mid[se] = 1;
        }
        // go down
        if (i + 2 <= n && a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W') {
            int fi = g(i, j), se = g(i + 1, j), th = g(i + 2, j);
            adj[fi].pb(se); adj[se].pb(th);

            c[fi][se] = c[se][fi] = 1;
            c[se][th] = c[th][se] = 1;

            st[fi] = en[th] = mid[se] = 1;
        }
    }

    t = n * m + 1;
    vector<int> node;
    rep(i, 1, n * m) {
        if (st[i]) {
            c[0][i] = c[i][0] = 1;
            adj[0].pb(i); adj[i].pb(0);
        }
        if (en[i]) {
            c[i][t] = c[t][i] = 1;
            adj[i].pb(t); adj[t].pb(i);
        }
        if (mid[i] && sz(adj[i]) == 2) node.pb(i);
    }

    int mx = 0;
    rep(i, 0, (1 << sz(node)) - 1) {
        memset(f, 0, sizeof f);
        rep(j, 0, sz(node) - 1) {
            int u = node[j], v = adj[u][getBit(i, j)];
            c[u][v] = c[v][u] = 0;
        }
        res = 0;
        while (bfs()) incflow();
        maximize(mx, res);

        rep(j, 0, sz(node) - 1) {
            int u = node[j], v = adj[u][getBit(i, j)];
            c[u][v] = c[v][u] = 1;
        }
    }
    cout << mx;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67