Submission #66867

#	Time	Username	Problem	Language	Result	Execution time	Memory
66867		cdemirer	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	2052 ms	263168 KiB

dango_maker

#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 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 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-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 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();
	
	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++;
	}
	/*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 (stderr)

dango_maker.cpp: In function 'int bfs(int, bool)':
dango_maker.cpp:41: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:50: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 func()':
dango_maker.cpp:94:23: 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:98:23: 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:102:23: 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]);
                     ~~^~~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp: In function 'int count_component(int)':
dango_maker.cpp:113: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:135:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edges[x].size(); i++) {
                   ~~^~~~~~~~~~~~~~~~~
dango_maker.cpp:140:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < edges[y].size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~

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