Submission #100471

#	Time	Username	Problem	Language	Result	Execution time	Memory
100471		square1001	Land of the Rainbow Gold (APIO17_rainbow)	C++14	11 / 100	25 ms	908 KiB

rainbow

#include "rainbow.h"
#include <queue>
#include <vector>
#include <cassert>
using namespace std;

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

bool river[55][55], vis[55][55];
void init(int R, int C, int sr, int sc, int M, char *S) {
	assert(R <= 50 && C <= 50);
	--sr, --sc;
	river[sr][sc] = true;
	for(int i = 0; i < M; ++i) {
		if(S[i] == 'N') --sr;
		if(S[i] == 'S') ++sr;
		if(S[i] == 'W') --sc;
		if(S[i] == 'E') ++sc;
		river[sr][sc] = true;
	}
}

int colour(int ar, int ac, int br, int bc) {
	--ar, --ac;
	for(int i = ar; i < br; ++i) {
		for(int j = ac; j < bc; ++j) {
			vis[i][j] = false;
		}
	}
	int ans = 0;
	for(int i = ar; i < br; ++i) {
		for(int j = ac; j < bc; ++j) {
			if(vis[i][j] || river[i][j]) continue;
			queue<pair<int, int> > que; que.push(make_pair(i, j));
			vis[i][j] = true;
			while(!que.empty()) {
				pair<int, int> u = que.front(); que.pop();
				for(int k = 0; k < 4; ++k) {
					int tx = u.first + dx[k], ty = u.second + dy[k];
					if(ar <= tx && tx < br && ac <= ty && ty < bc && !river[tx][ty] && !vis[tx][ty]) {
						vis[tx][ty] = true;
						que.push(make_pair(tx, ty));
					}
				}
			}
			++ans;
		}
	}
	return ans;
}

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