This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<vi> vvi;
typedef pair<double, double> dodo;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
int N, M;
vvi edges;
int num_nodes = 0;
int createNode() {
edges.pb(vi());
return num_nodes++;
}
void connect(int a, int b) {
edges[a].pb(b);
edges[b].pb(a);
}
const int ARRSIZE = 3000*3000;
int parent[ARRSIZE];
bool vis[ARRSIZE] = {0};
/*int dpi[ARRSIZE], dpe[ARRSIZE];
void dfs(int x) {
vis[x] = true;
int no = -1;
for (int i = 0; i < edges[x].size(); i++) {
int y = edges[x][i];
if (y == parent[x]) continue;
if (vis[y]) {
no = i;
continue;
}
parent[y] = x;
dfs(y);
}
dpi[x] = 1;
for (int i = 0; i < edges[x].size(); i++) {
int y = edges[x][i];
if (y == parent[x]) continue;
if (y == no) continue;
dpi[x] += dpe[y];
}
dpe[x] = 0;
for (int i = 0; i < edges[x].size(); i++) {
int y = edges[x][i];
if (y == parent[x]) continue;
if (y == no) continue;
dpe[x] += max(dpi[y], dpe[y]);
}
}*/
int bfs(int x, bool b) {
int ret = 0;
queue<ii> Q;
Q.push(mp(x, (int)b));
while (!Q.empty()) {
ii a = Q.front(); Q.pop();
if (vis[a.first]) continue;
vis[a.first] = true;
ret += a.second;
for (int i = 0; i < edges[a.first].size(); i++) {
int y = edges[a.first][i];
Q.push(mp(y, !a.second));
}
}
return ret;
}
void clean(int x) {
vis[x] = false;
for (int i = 0; i < edges[x].size(); i++) {
int y = edges[x][i];
if (!vis[y]) continue;
clean(y);
}
}
int mat[3000][3000];
vi touch[3000][3000];
void memory_opt() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
string s; cin >> s;
for (int j = 0; j < M; j++) {
if (s[j] == 'R') mat[i][j] = 0;
if (s[j] == 'G') mat[i][j] = 1;
if (s[j] == 'W') mat[i][j] = 2;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M-2; j++) {
if (mat[i][j]*9 + mat[i][j+1]*3 + mat[i][j+2]*1 == 5) {
int x = createNode();
if (touch[i][j].size() > 0) {
for (int k = 0; k < touch[i][j].size(); k++) connect(x, touch[i][j][k]);
}
touch[i][j].pb(x);
if (touch[i][j+1].size() > 0) {
for (int k = 0; k < touch[i][j+1].size(); k++) connect(x, touch[i][j+1][k]);
}
touch[i][j+1].pb(x);
if (touch[i][j+2].size() > 0) {
for (int k = 0; k < touch[i][j+2].size(); k++) connect(x, touch[i][j+2][k]);
}
touch[i][j+2].pb(x);
}
}
}
for (int i = 0; i < N-2; i++) {
for (int j = 0; j < M; j++) {
if (mat[i][j]*9 + mat[i+1][j]*3 + mat[i+2][j]*1 == 5) {
int x = createNode();
if (touch[i][j].size() > 0) {
for (int k = 0; k < touch[i][j].size(); k++) connect(x, touch[i][j][k]);
}
touch[i][j].pb(x);
if (touch[i+1][j].size() > 0) {
for (int k = 0; k < touch[i+1][j].size(); k++) connect(x, touch[i+1][j][k]);
}
touch[i+1][j].pb(x);
if (touch[i+2][j].size() > 0) {
for (int k = 0; k < touch[i+2][j].size(); k++) connect(x, touch[i+2][j][k]);
}
touch[i+2][j].pb(x);
}
}
}
}
int main(int argc, char **argv) {
ios_base::sync_with_stdio(0);
cin.tie(0);
memory_opt();
//cerr << num_nodes << endl;
int sum = 0;
for (int i = 0; i < num_nodes; i++) {
if (vis[i]) continue;
//parent[i] = -1;
int a = bfs(i, true);
clean(i);
int b = bfs(i, false);
sum += max(a, b);
//sum += max(dpi[i], dpe[i]);
//cerr << "i am " << i << " i added " << max(dpi[i], dpe[i]) << endl;
}
cout << sum << endl;
return 0;
}
Compilation message (stderr)
dango_maker.cpp: In function 'int bfs(int, bool)':
dango_maker.cpp:69:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges[a.first].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp: In function 'void clean(int)':
dango_maker.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges[x].size(); i++) {
~~^~~~~~~~~~~~~~~~~
dango_maker.cpp: In function 'void memory_opt()':
dango_maker.cpp:103:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < touch[i][j].size(); k++) connect(x, touch[i][j][k]);
~~^~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:107:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < touch[i][j+1].size(); k++) connect(x, touch[i][j+1][k]);
~~^~~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:111:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < touch[i][j+2].size(); k++) connect(x, touch[i][j+2][k]);
~~^~~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:122:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < touch[i][j].size(); k++) connect(x, touch[i][j][k]);
~~^~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:126:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < touch[i+1][j].size(); k++) connect(x, touch[i+1][j][k]);
~~^~~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:130:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = 0; k < touch[i+2][j].size(); k++) connect(x, touch[i+2][j][k]);
~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |