Submission #66752

#	Time	Username	Problem	Language	Result	Execution time	Memory
66752		cdemirer	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	210 ms	212236 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 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]);
	}
}

void memory_opt() {
	int mat[3000][3000];
	vi touch[3000][3000];
	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;
		dfs(i);
		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 'void dfs(int)':
dango_maker.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edges[x].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~
dango_maker.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edges[x].size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~
dango_maker.cpp:53: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:78: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:82: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:86: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:97: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:101: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:105: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]);
                      ~~^~~~~~~~~~~~~~~~~~~~~~

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