#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)
#define INF 1000000005
#define TYPE ii
typedef struct Node {
TYPE k;
int p;
Node *l, *r;
int sz;
TYPE mn;
/*Node(TYPE param) {
k = param;
p = rand();
l = r = 0;
sz = 1;
mn = param;
}*/
} Node;
Node noderez[9000000];
int rezcnt = 0;
queue<Node*> freerez;
Node* newNode(TYPE param) {
Node *ret;
if (freerez.empty()) ret = &(noderez[rezcnt++]);
else {
ret = freerez.front();
freerez.pop();
}
ret->k = param;
ret->p = rand();
ret->l = ret->r = 0;
ret->sz = 1;
ret->mn = param;
return ret;
}
typedef pair<Node*, Node*> NodepNodep;
void update(Node *x) {
if (!x) return;
x->sz = (x->l ? x->l->sz : 0) + 1 + (x->r ? x->r->sz : 0);
x->mn = (x->l ? x->l->mn : x->k);
}
NodepNodep split(Node *r, TYPE k) {
NodepNodep nn;
if (!r) {
nn.first = nn.second = nullptr;
} else if (k <= r->k) {
nn.second = r;
NodepNodep res = split(r->l, k);
nn.first = res.first;
r->l = res.second;
update(nn.first);
update(nn.second);
} else {
nn.first = r;
NodepNodep res = split(r->r, k);
r->r = res.first;
nn.second = res.second;
update(nn.first);
update(nn.second);
}
return nn;
}
NodepNodep splitAlt(Node *r, int ind) {
NodepNodep nn;
if (!r) {
nn.first = nn.second = nullptr;
} else if ((r->l ? r->l->sz : 0) >= ind) {
nn.second = r;
NodepNodep res = splitAlt(r->l, ind);
nn.first = res.first;
r->l = res.second;
update(nn.first);
update(nn.second);
} else {
nn.first = r;
NodepNodep res = splitAlt(r->r, ind-1-(r->l ? r->l->sz : 0));
r->r = res.first;
nn.second = res.second;
update(nn.first);
update(nn.second);
}
return nn;
}
bool exists(Node *r, TYPE k) {
if (!r) return false;
else if (r->k == k) return true;
else if (k < r->k) return exists(r->l, k);
else return exists(r->r, k);
}
Node* insert(Node *r, Node *n) {
Node *ret;
if (!r) {
ret = n;
update(ret);
} else if (n->p > r->p) {
NodepNodep res = split(r, n->k);
n->l = res.first;
n->r = res.second;
ret = n;
update(ret);
} else {
if (n->k < r->k) {
r->l = insert(r->l, n);
} else {
r->r = insert(r->r, n);
}
ret = r;
update(ret);
}
return ret;
}
Node* merge(Node *l, Node *r) {
Node *ret;
if (!l) ret = r;
else if (!r) ret = l;
else {
if (l->p > r->p) {
Node *res = merge(l->r, r);
l->r = res;
ret = l;
} else {
Node *res = merge(l, r->l);
r->l = res;
ret = r;
}
update(ret);
}
return ret;
}
Node* erase(Node *r, TYPE k) {
Node *ret;
if (!r) ret = nullptr;
else if (r->k == k) {
freerez.push(r);
ret = merge(r->l, r->r);
update(ret);
} else {
if (k < r->k) {
r->l = erase(r->l, k);
} else {
r->r = erase(r->r, k);
}
ret = r;
update(ret);
}
return ret;
}
/*void traversePrint(Node *r) {
if (!r) return;
if (r->l) traversePrint(r->l);
cerr << r->k << " (" << r->p << ") ";
if (r->r) traversePrint(r->r);
}*/
#undef TYPE
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 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];
int touch[3000][3000][2];
void func() {
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; j++) touch[i][j][0] = touch[i][j][1] = -1;
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]);
}*/
if (touch[i][j][0] != -1) touch[i][j][1] = x;
else touch[i][j][0] = x;
//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]);
}*/
if (touch[i][j+1][0] != -1) touch[i][j+1][1] = x;
else touch[i][j+1][0] = x;
//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]);
}*/
if (touch[i][j+2][0] != -1) touch[i][j+2][1] = x;
else touch[i][j+2][0] = x;
//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]);
if (touch[i][j][0] != -1) connect(x, touch[i][j][0]);
if (touch[i][j][1] != -1) connect(x, touch[i][j][1]);
//}
//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]);
if (touch[i+1][j][0] != -1) connect(x, touch[i+1][j][0]);
if (touch[i+1][j][1] != -1) connect(x, touch[i+1][j][1]);
//}
//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]);
if (touch[i+2][j][0] != -1) connect(x, touch[i+2][j][0]);
if (touch[i+2][j][1] != -1) connect(x, touch[i+2][j][1]);
//}
//touch[i+2][j].pb(x);
}
}
}
}
int count_component(int x) {
vis[x] = true;
int ret = 1;
for (int i = 0; i < edges[x].size(); i++) {
int y = edges[x][i];
if (vis[y]) continue;
ret += count_component(y);
}
return ret;
}
int es[ARRSIZE] = {0};
int main(int argc, char **argv) {
ios_base::sync_with_stdio(0);
cin.tie(0);
func();
//if (N > 2999 && M > 2999) exit(-1);
/*int sum = 0;
set<ii> S;
for (int i = 0; i < num_nodes; i++) es[i] = edges[i].size();
for (int i = 0; i < num_nodes; i++) S.insert(mp(es[i], i));
while (!S.empty()) {
int x = (*S.begin()).second;
S.erase(S.begin());
for (int i = 0; i < edges[x].size(); i++) {
int y = edges[x][i];
auto it = S.find(mp(es[y], y));
if (it != S.end()) {
S.erase(it);
for (int j = 0; j < edges[y].size(); j++) {
int y2 = edges[y][j];
auto it2 = S.find(mp(es[y2], y2));
if (it2 != S.end()) {
S.erase(it2);
es[y2]--;
S.insert(mp(es[y2], y2));
}
}
}
}
sum++;
}*/
int sum = 0;
srand(time(0));
Node *root = nullptr;
for (int i = 0; i < num_nodes; i++) es[i] = edges[i].size();
for (int i = 0; i < num_nodes; i++) {
Node *n = newNode(mp(es[i], i));
root = insert(root, n);
}
while (root != nullptr) {
int x = root->mn.second;
root = erase(root, mp(es[x], x));
for (int i = 0; i < edges[x].size(); i++) {
int y = edges[x][i];
if (exists(root, mp(es[y], y))) {
root = erase(root, mp(es[y], y));
for (int j = 0; j < edges[y].size(); j++) {
int y2 = edges[y][j];
if (exists(root, mp(es[y2], y2))) {
root = erase(root, mp(es[y2], y2));
es[y2]--;
Node *n = newNode(mp(es[y2], y2));
root = insert(root, n);
}
}
}
}
sum++;
}
/*for (int i = 0; i < num_nodes; i++) {
if (vis[i]) continue;
int a = bfs(i, true);
clean(i);
int b = bfs(i, false);
assert(abs(a-b) <= 1);
sum += max(a, b);
}*/
cout << sum << endl;
return 0;
}
Compilation message
dango_maker.cpp: In function 'int bfs(int, bool)':
dango_maker.cpp:194: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:203: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 'int count_component(int)':
dango_maker.cpp:279: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 'int main(int, char**)':
dango_maker.cpp:332:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges[x].size(); i++) {
~~^~~~~~~~~~~~~~~~~
dango_maker.cpp:336:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < edges[y].size(); j++) {
~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
546 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
546 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
546 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
