Submission #197001

#	Time	Username	Problem	Language	Result	Execution time	Memory
197001		combi1k1	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	247 ms	212600 KiB

dango_maker

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 3005;

typedef pair<int,int>   ii;

char a[N][N];
int  t[N][N];

struct Edge {
    int v, c;
    Edge(int _v,int _c) : v(_v), c(_c)  {}
};

vector<Edge> E;
vector<int>  g[N * N];

void addEdge(int u,int v,int c) {
    g[u].pb(sz(E)); E.pb(v,c);
    g[v].pb(sz(E)); E.pb(u,0);
}

int S, T;
int d[N * N];
int p[N * N];

bool bfs()  {
    for(int i = 0 ; i <= T ; ++i)
        d[i] = -1,
        p[i] = 0;

    queue<int>  q;
    q.push(S);  d[S] = 0;

    while (q.size())    {
        int u = q.front();  q.pop();
        for(int i : g[u])   {
            int v = E[i].v;
            if (E[i].c == 0)    continue;
            if (d[v] < 0)   {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }

    return  d[T] >= 0;
}

int dfs(int u,int F)    {
    if (u == T || F == 0)   return  F;
    for(int &i = p[u] ; i < sz(g[u]) ; ++i)  {
        int j = g[u][i];
        int v = E[j].v;
        if (E[j].c == 0 || d[v] != d[u] + 1)
            continue;
        int res = dfs(v,min(E[j].c,F));
        if (res)    {
            E[j].c -= res;  j ^= 1;
            E[j].c += res;  return  res;
        }
    }
    return  0;
}

int MaxFlow()   {
    while (bfs())
    while (dfs(S,1));

    int ans = 0;

    for(int i : g[T])
        ans += E[i].c;

    return  ans;
}

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

    int n;  cin >> n;
    int m;  cin >> m;

    int cnt = 0;

    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < m ; ++j)    {
        cin >> a[i][j];

        if (a[i][j] != 'G')
            t[i][j] = cnt++;

        if (a[i][j] == 'W') {
            if (i > 1 && a[i - 1][j] == 'G' && a[i - 2][j] == 'R')
                addEdge(t[i][j],t[i - 2][j],1);
            if (j > 1 && a[i][j - 1] == 'G' && a[i][j - 2] == 'R')
                addEdge(t[i][j],t[i][j - 2],1);
        }
    }
    S = cnt;
    T = cnt + 1;

    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < m ; ++j)    {
        if (a[i][j] == 'W') addEdge(S,t[i][j],1);
        if (a[i][j] == 'R') addEdge(t[i][j],T,1);
    }

    cout << MaxFlow() << endl;
}

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