oj.uz

Submission #375692

# Submission time Handle Problem Language Result Execution time Memory
375692 2021-03-09T16:56:45 Z peijar Dango Maker (JOI18_dango_maker) C++17
33 / 100
 63 ms 23020 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN =3000;
char couleur[MAXN][MAXN];
int idDumpling[MAXN][MAXN];
vector<int> adj[MAXN];
int matchAvec[MAXN];
bool vu[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
 */

bool dfs(int u)
{
	if (vu[u]) return false;
	vu[u] = true;
	for (auto v : adj[u])
		if (matchAvec[v] == -1 or dfs(matchAvec[v]))
		{
			matchAvec[v] = u;
			return true;
		}
	return false;
}


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 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')
				idDumpling[iLig][iCol] = nbVu++;
		}
	int nbGauche = nbVu;
	nbVu = 0;
	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
				matchAvec[nbVu] = -1;
				if (idDumpling[iLig][iCol] != -1)
					adj[idDumpling[iLig][iCol]].push_back(nbVu);
				if (iLig and idDumpling[iLig-1][iCol+1] != -1)
					adj[idDumpling[iLig-1][iCol+1]].push_back(nbVu);
				if (iLig > 1 and idDumpling[iLig-2][iCol+2] != -1)
					adj[idDumpling[iLig-2][iCol+2]].push_back(nbVu);
				++nbVu;
			}
	int maxMatching(0);
	for (int i(0); i < nbGauche; ++i)
	{
		fill(vu, vu + nbGauche, false);
		maxMatching += dfs(i);
	}
	int ret = nbDumplingsPotentiels - maxMatching;
	cout << ret << endl;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Correct 1 ms 492 KB Output is correct
22 Correct 1 ms 492 KB Output is correct
23 Correct 1 ms 492 KB Output is correct
24 Correct 1 ms 492 KB Output is correct
25 Correct 1 ms 492 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 492 KB Output is correct
28 Correct 1 ms 492 KB Output is correct
29 Correct 1 ms 492 KB Output is correct
30 Correct 1 ms 492 KB Output is correct
31 Correct 1 ms 492 KB Output is correct
32 Correct 1 ms 492 KB Output is correct
33 Correct 1 ms 492 KB Output is correct
34 Correct 1 ms 492 KB Output is correct
35 Correct 1 ms 512 KB Output is correct
36 Correct 1 ms 492 KB Output is correct
37 Correct 1 ms 512 KB Output is correct
38 Correct 1 ms 492 KB Output is correct
39 Correct 1 ms 492 KB Output is correct
40 Correct 1 ms 492 KB Output is correct
41 Correct 1 ms 492 KB Output is correct
42 Correct 1 ms 492 KB Output is correct
43 Correct 1 ms 492 KB Output is correct
44 Correct 1 ms 492 KB Output is correct
45 Correct 1 ms 492 KB Output is correct
46 Correct 1 ms 492 KB Output is correct
47 Correct 1 ms 492 KB Output is correct
48 Correct 1 ms 492 KB Output is correct
49 Correct 1 ms 492 KB Output is correct
50 Correct 1 ms 492 KB Output is correct
51 Correct 1 ms 492 KB Output is correct
52 Correct 1 ms 492 KB Output is correct
53 Correct 1 ms 492 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Correct 1 ms 492 KB Output is correct
22 Correct 1 ms 492 KB Output is correct
23 Correct 1 ms 492 KB Output is correct
24 Correct 1 ms 492 KB Output is correct
25 Correct 1 ms 492 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 492 KB Output is correct
28 Correct 1 ms 492 KB Output is correct
29 Correct 1 ms 492 KB Output is correct
30 Correct 1 ms 492 KB Output is correct
31 Correct 1 ms 492 KB Output is correct
32 Correct 1 ms 492 KB Output is correct
33 Correct 1 ms 492 KB Output is correct
34 Correct 1 ms 492 KB Output is correct
35 Correct 1 ms 512 KB Output is correct
36 Correct 1 ms 492 KB Output is correct
37 Correct 1 ms 512 KB Output is correct
38 Correct 1 ms 492 KB Output is correct
39 Correct 1 ms 492 KB Output is correct
40 Correct 1 ms 492 KB Output is correct
41 Correct 1 ms 492 KB Output is correct
42 Correct 1 ms 492 KB Output is correct
43 Correct 1 ms 492 KB Output is correct
44 Correct 1 ms 492 KB Output is correct
45 Correct 1 ms 492 KB Output is correct
46 Correct 1 ms 492 KB Output is correct
47 Correct 1 ms 492 KB Output is correct
48 Correct 1 ms 492 KB Output is correct
49 Correct 1 ms 492 KB Output is correct
50 Correct 1 ms 492 KB Output is correct
51 Correct 1 ms 492 KB Output is correct
52 Correct 1 ms 492 KB Output is correct
53 Correct 1 ms 492 KB Output is correct
54 Correct 1 ms 492 KB Output is correct
55 Correct 11 ms 21228 KB Output is correct
56 Correct 2 ms 492 KB Output is correct
57 Correct 10 ms 14316 KB Output is correct
58 Runtime error 63 ms 23020 KB Execution killed with signal 11
59 Halted 0 ms 0 KB -