Submission #409177

#	Time	Username	Problem	Language	Result	Execution time	Memory
409177		cheissmart	Land of the Rainbow Gold (APIO17_rainbow)	C++14	11 / 100	3089 ms	1048580 KiB

rainbow

#ifndef CHEISSMART
#include "rainbow.h"
#endif
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7;

int di[] = {1, -1, 0, 0}, dj[] = {0, 0, 1, -1};

V<pi> bad;
int R, C;

void init(int R, int C, int sr, int sc, int M, char *S) {
	::R = R, ::C = C;
	bad.EB(sr - 1, sc - 1);
	for(int i = 0; i < M; i++) {
		if(S[i] == 'N') sr--;
		else if(S[i] == 'S') sr++;
		else if(S[i] == 'W') sc--;
		else sc++;
		bad.EB(sr - 1, sc - 1);
	}
	sort(ALL(bad));
	bad.resize(unique(ALL(bad)) - bad.begin());
}

int colour(int ar, int ac, int br, int bc) {
	ar--, ac--, br--, bc--;
	V<vi> vis(R, vi(C));
	for(pi p:bad)
		vis[p.F][p.S] = 1;
 	auto ok = [&] (int i, int j) {
		return ar <= i && i <= br && ac <= j && j <= bc && vis[i][j] == 0;
	};
	function<void(int, int)> dfs = [&] (int i, int j) {
		vis[i][j] = 1;
		for(int k = 0; k < 4; k++) {
			int ii = i + di[k], jj = j + dj[k];
			if(ok(ii, jj))
				dfs(ii, jj);
		}
	};

	int cnt = 0;
	for(int i = ar; i <= br; i++) {
		for(int j = ac; j <= bc; j++) {
			if(vis[i][j] == 0) {
				cnt++;
				dfs(i, j);
			}
		}
	}
	debug(cnt);
	return cnt;
}

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