Submission #126363

#	Time	Username	Problem	Language	Result	Execution time	Memory
126363		EntityIT	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	2 ms	420 KiB

dango_maker

#include<bits/stdc++.h>

using namespace std;

#define pb push_back

const int inf = (int)1e9 + 123, N = (int)3e3 + 5, M = N;
int n, m;
char c[N][M];

struct MaxFlow {
    int nVer, src, snk;
    struct Edge {
        int u, v, cap, f;
        Edge(int _u, int _v, int _cap, int _f) : u(_u), v(_v), cap(_cap), f(_f) {}
    };
    vector< vector<int> > gr;
    vector<Edge> edge;
    vector<int> d, iGr;
    MaxFlow(int _nVer = 0, int _src = 0, int _snk = 0) : nVer(_nVer), src(_src), snk(_snk) { edge.clear(); gr.assign(nVer + 5, vector<int>() ); }
    void addEdge(int u, int v, int cap) {
        gr[u].pb( (int)edge.size() ); edge.pb(Edge(u, v, cap, 0) );
        gr[v].pb( (int)edge.size() ); edge.pb(Edge(v, u, 0, 0) );
    }
    bool bfs() {
        d.assign(nVer + 5, inf); d[src] = 0; iGr.assign(nVer + 5, 0);
        queue<int> q; q.push(src);
        while(!q.empty() ) {
            int u = q.front(); q.pop();
            for (int id : gr[u]) if(d[ edge[id].v ] == inf && edge[id].f < edge[id].cap) d[ edge[id].v ] = d[u] + 1, q.push(edge[id].v);
        }
        return d[snk] != inf;
    }
    int dfs(int u, int flow) {
        if(u == snk || !flow) return flow;
        for (int &i = iGr[u]; i < (int)gr[u].size(); ++i) {
            int id = gr[u][i];
            if(d[ edge[id].v ] != d[u] + 1 || edge[id].f >= edge[id].cap) continue;
            int nex = dfs(edge[id].v, min(flow, edge[id].cap - edge[id].f) );
            if(nex) { edge[id].f += nex; edge[id ^ 1].f -= nex; return nex; }
        }
        return 0;
    }
    int solve() {
        while(bfs() ) while(dfs(src, inf) );
        int ret = 0;
        for (int id : gr[src]) ret += edge[id].f;
        return ret;
    }
};

int _1D (int x, int y) { return (x - 1) * m + y; }
int prv (int x, int y) { return _1D(x, y) * 2 - 1; }
int nxt (int x, int y) { return _1D(x, y) * 2; }

int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) cin >> c[i][j];
    }

    MaxFlow mf(2 + 2 * n * m, 0, 1 + 2 * n * m);

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            mf.addEdge(prv(i, j), nxt(i, j), 1);
            if (c[i][j] == 'R') mf.addEdge(mf.src, prv(i, j), 1);
            if (c[i][j] == 'W') mf.addEdge(nxt(i, j), mf.snk, 1);
            if (c[i][j] == 'R' && c[i][j + 1] == 'G') mf.addEdge(nxt(i, j), prv(i, j + 1), 1);
            if (c[i][j] == 'R' && c[i + 1][j] == 'G') mf.addEdge(nxt(i, j), prv(i + 1, j), 1);
            if (c[i][j] == 'G' && c[i][j + 1] == 'W') mf.addEdge(nxt(i, j), prv(i, j + 1), 1);
            if (c[i][j] == 'G' && c[i + 1][j] == 'W') mf.addEdge(nxt(i, j), prv(i + 1, j), 1);
        }
    }

    cout << mf.solve();

    return 0;
}

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