제출 #375659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375659		peijar	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	568 ms	262144 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;

const int MAXN =3000;
char couleur[MAXN][MAXN];
bool pris[MAXN][MAXN];
int idDumpling[MAXN][MAXN];

/*   	 x
 *   x 
 * . . .  
 *
 * 		.
 * 	x	.
 * x  .
 * Graphe biparti : on cherche max independent set 
 * si S independant max, si e arete, une extremité pas dans S !
 * Donc complementaire de S = min vertex cover
 * Donc nbDumplingsPotentiels - maxMatch = rep
 */

struct Edge
{
	int to, f, c;
};

struct Graph
{
	vector<Edge> edges;
	vector<vector<int>> G;
	int s, t;
	Graph(int n, int s, int t) : edges(), G(n), s(s), t(t) {}

	void addEdge(int a, int b, int c1, int c2=0)
	{
		G[a].push_back(edges.size());
		edges.push_back(Edge{b, 0, c1});
		G[b].push_back(edges.size());
		edges.push_back(Edge{a, 0, c2});
	}
};

struct Dinic : public Graph
{
	vector<int> dis, ptr;
	Dinic(int n, int s, int t) : Graph(n, s, t) {}

	int dfs(int v, int maxF)
	{
		if (v == t or !maxF) return maxF;
		for (; ptr[v] < (int)G[v].size(); ++ptr[v])
		{
			int k= G[v][ptr[v]];
			Edge &ed = edges[k];
			if (ed.c > ed.f and dis[ed.to] == dis[v] + 1)
				if (ed.c > ed.f and dis[ed.to] == dis[v] + 1)
					if (int df = dfs(ed.to, min(maxF, ed.c - ed.f)))
					{
						ed.f += df;
						edges[k^1].f -= df;
						return df;
					}
		}
		return 0;
	}
	
	int flow()
	{
		int N = G.size();
		int f(0);
		while (1)
		{
			dis.assign(N, -1);
			queue<int> q; q.push(s); dis[s] = 0;
			while (!q.empty())
			{
				int u = q.front(); q.pop();
				if (u == t) break;
				for (auto k : G[u])
				{
					Edge ed = edges[k];
					if (ed.c > ed.f and dis[ed.to] == -1)
					{
						dis[ed.to] = dis[u] + 1;
						q.push(ed.to);
					}
				}
			}
			if (dis[t] == -1) break;
			ptr.assign(N, 0);
			while (int df = dfs(s, (1 << 30))) f += df;
		}
		return f;
	}
};


signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbLig, nbCol;
	cin >> nbLig >> nbCol;
	for (int iLig(0); iLig < nbLig; ++iLig)
		for (int iCol(0); iCol < nbCol; ++iCol)
			cin >> couleur[iLig][iCol];
	int nbDumplingsPotentiels(0);
	for (int iLig(0); iLig < nbLig; ++iLig)
		for (int iCol(0); iCol < nbCol; ++iCol)
		{
			if (iLig + 2 < nbLig and couleur[iLig][iCol] == 'R'
					and couleur[iLig+1][iCol] == 'G' and couleur[iLig+2][iCol] == 'W')
				nbDumplingsPotentiels++;
			if (iCol+2 < nbCol and couleur[iLig][iCol] == 'R' and 
					couleur[iLig][iCol+1] == 'G' and couleur[iLig][iCol+2] == 'W')
				nbDumplingsPotentiels++;
		}
	int s = nbDumplingsPotentiels;
	int t = nbDumplingsPotentiels+1;
	Dinic dic(nbDumplingsPotentiels+2, s, t);
	int nbVu(0);
	for (int iLig(0); iLig < nbLig; ++iLig)
		for (int iCol(0); iCol < nbCol; ++iCol)
		{
			idDumpling[iLig][iCol] = -1;
			if (iLig + 2 < nbLig and couleur[iLig][iCol] == 'R'
					and couleur[iLig+1][iCol] == 'G' and couleur[iLig+2][iCol] == 'W')
			{
				dic.addEdge(s, nbVu, 1);
				idDumpling[iLig][iCol] = nbVu++;
			}
		}
	for (int iLig(0); iLig < nbLig; ++iLig)
		for (int iCol(0); iCol < nbCol; ++iCol)
			if (iCol+2 < nbCol and couleur[iLig][iCol] == 'R' and 
					couleur[iLig][iCol+1] == 'G' and couleur[iLig][iCol+2] == 'W')
			{
				// R G W
				if (idDumpling[iLig][iCol] != -1)
					dic.addEdge(idDumpling[iLig][iCol], nbVu, 1);
				if (iLig and idDumpling[iLig-1][iCol+1] != -1)
					dic.addEdge(idDumpling[iLig-1][iCol+1], nbVu, 1);
				if (iLig > 1 and idDumpling[iLig-2][iCol+2] != -1)
					dic.addEdge(idDumpling[iLig-2][iCol+2], nbVu, 1);
				dic.addEdge(nbVu++, t, 1);
			}
	int ret = nbDumplingsPotentiels - dic.flow();
	cout << ret << endl;
}

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