#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;
}
# |
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 |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
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 |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
364 KB |
Output is correct |
34 |
Correct |
1 ms |
364 KB |
Output is correct |
35 |
Correct |
1 ms |
364 KB |
Output is correct |
36 |
Correct |
1 ms |
364 KB |
Output is correct |
37 |
Correct |
1 ms |
364 KB |
Output is correct |
38 |
Correct |
1 ms |
364 KB |
Output is correct |
39 |
Correct |
1 ms |
364 KB |
Output is correct |
40 |
Correct |
1 ms |
364 KB |
Output is correct |
41 |
Correct |
1 ms |
364 KB |
Output is correct |
42 |
Correct |
1 ms |
396 KB |
Output is correct |
43 |
Correct |
1 ms |
364 KB |
Output is correct |
44 |
Correct |
1 ms |
364 KB |
Output is correct |
45 |
Correct |
1 ms |
364 KB |
Output is correct |
46 |
Correct |
1 ms |
364 KB |
Output is correct |
47 |
Correct |
1 ms |
364 KB |
Output is correct |
48 |
Correct |
1 ms |
364 KB |
Output is correct |
49 |
Correct |
1 ms |
364 KB |
Output is correct |
50 |
Correct |
1 ms |
364 KB |
Output is correct |
51 |
Correct |
1 ms |
364 KB |
Output is correct |
52 |
Correct |
1 ms |
364 KB |
Output is correct |
53 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
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 |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
364 KB |
Output is correct |
34 |
Correct |
1 ms |
364 KB |
Output is correct |
35 |
Correct |
1 ms |
364 KB |
Output is correct |
36 |
Correct |
1 ms |
364 KB |
Output is correct |
37 |
Correct |
1 ms |
364 KB |
Output is correct |
38 |
Correct |
1 ms |
364 KB |
Output is correct |
39 |
Correct |
1 ms |
364 KB |
Output is correct |
40 |
Correct |
1 ms |
364 KB |
Output is correct |
41 |
Correct |
1 ms |
364 KB |
Output is correct |
42 |
Correct |
1 ms |
396 KB |
Output is correct |
43 |
Correct |
1 ms |
364 KB |
Output is correct |
44 |
Correct |
1 ms |
364 KB |
Output is correct |
45 |
Correct |
1 ms |
364 KB |
Output is correct |
46 |
Correct |
1 ms |
364 KB |
Output is correct |
47 |
Correct |
1 ms |
364 KB |
Output is correct |
48 |
Correct |
1 ms |
364 KB |
Output is correct |
49 |
Correct |
1 ms |
364 KB |
Output is correct |
50 |
Correct |
1 ms |
364 KB |
Output is correct |
51 |
Correct |
1 ms |
364 KB |
Output is correct |
52 |
Correct |
1 ms |
364 KB |
Output is correct |
53 |
Correct |
1 ms |
364 KB |
Output is correct |
54 |
Correct |
1 ms |
364 KB |
Output is correct |
55 |
Correct |
13 ms |
21228 KB |
Output is correct |
56 |
Correct |
2 ms |
748 KB |
Output is correct |
57 |
Correct |
9 ms |
14572 KB |
Output is correct |
58 |
Correct |
64 ms |
20136 KB |
Output is correct |
59 |
Correct |
568 ms |
118052 KB |
Output is correct |
60 |
Correct |
542 ms |
118120 KB |
Output is correct |
61 |
Correct |
536 ms |
118172 KB |
Output is correct |
62 |
Correct |
1 ms |
512 KB |
Output is correct |
63 |
Correct |
561 ms |
115692 KB |
Output is correct |
64 |
Runtime error |
458 ms |
262144 KB |
Execution killed with signal 9 |
65 |
Halted |
0 ms |
0 KB |
- |