Submission #1117164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117164		pedroslrey	Land of the Rainbow Gold (APIO17_rainbow)	C++17	11 / 100	3054 ms	1048576 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<bool>> M;

void init(int n, int m, int sx, int sy, int sl, char *serp) {
	M.assign(n, vector<bool>(m));

	--sx; --sy;
	map<char, int> sdx{{'N', -1}, {'S', 1}};
	map<char, int> sdy{{'W', -1}, {'E', 1}};
	M[sx][sy] = true;
	for (int i = 0; i < sl; ++i) {
		char c = serp[i];

		sx += sdx[c]; sy += sdy[c];
		M[sx][sy] = true;
	}

	// int comp = 0;
	// pref.assign(n, vector<int>(m));
	// for (int i = 0; i < n; ++i)
	// 	for (int j = 0; j < m; ++j)
	// 		if (M[i][j] == 0) {
	// 			pref[i][j] = 1;
	// 			pos.emplace_back(i, j);
	// 			dfs(i, j, ++comp);
	// 		}

	// for (int i = 0; i < n; ++i)
	// 	for (int j = 0; j < m; ++j)
	// 		pref[i][j] += (i > 0 ? pref[i-1][j] : 0) 
	// 					+ (j > 0 ? pref[i][j-1] : 0) 
	// 					- (i > 0 && j > 0 ? pref[i-1][j-1] : 0);
}

// int grid_sum(int x1, int y1, int x2, int y2) {
// 	return pref[x2][y2]
// 		   - (x1 > 0 ? pref[x1 - 1][y2] : 0)
// 		   - (y1 > 0 ? pref[x2][y1 - 1] : 0) 
// 		   + (x1 > 0 && y1 > 0 ? pref[x1 - 1][y1 - 1] : 0);
// }

int colour(int x1, int y1, int x2, int y2) {
	--x1; --y1; --x2; --y2;	

	static vector<vector<bool>> marc;
	marc.assign(M.size(), vector<bool>(M[0].size()));

	function<void (int, int)> dfs = [&](int x, int y) {
		marc[x][y] = true;

		static vector<int> dx{1, 0, -1, 0};
		static vector<int> dy{0, 1, 0, -1};

		for (int k = 0; k < 4; ++k) {
			int nx = x + dx[k], ny = y + dy[k];

			if (nx < x1 || nx > x2 || ny < y1 || ny > y2) continue;
			if (M[nx][ny] || marc[nx][ny]) continue;

			dfs(nx, ny);
		}
	};

	int ans = 0;
	for (int i = x1; i <= x2; ++i) 
		for (int j = y1; j <= y2; ++j) 
			if (!M[i][j] && !marc[i][j]) {
				++ans;
				dfs(i, j);
			}

	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26