Submission #262900

#	Time	Username	Problem	Language	Result	Execution time	Memory
262900		Saboon	Land of the Rainbow Gold (APIO17_rainbow)	C++14	11 / 100	22 ms	896 KiB

rainbow

#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;

map<char,int> adjr = {{'N', -1}, {'S', 1}};
map<char,int> adjc = {{'E', 1}, {'W', -1}};
int R, C;
bool mark[52][52];
int par[52*52];

int get_par(int v){
	return par[v] < 0 ? v : par[v] = get_par(par[v]);
}

bool merge(int v, int u){
	if ((v = get_par(v)) == (u = get_par(u)))
		return false;
	if (par[v] > par[u])
		swap(v, u);
	par[u] = v;
	return true;
}

void init(int r, int c, int sr, int sc, int M, char* s){
	R = r, C = c;
	mark[sr][sc] = 1;
	for (int i = 0; i < M; i++){
		sr += adjr[s[i]], sc += adjc[s[i]];
		mark[sr][sc] = 1;
	}
}

int colour(int x1, int y1, int x2, int y2){
	int cnt = 0;
	memset(par, -1, sizeof par);
	for (int i = x1; i <= x2; i++){
		for (int j = y1; j <= y2; j++){
			if (mark[i][j])
				continue;
			cnt ++;
			if (i > x1 and !mark[i-1][j])
				cnt -= merge((i-1)*C+j, (i-2)*C+j);
			if (j > y1 and !mark[i][j-1])
				cnt -= merge((i-1)*C+j, (i-1)*C+j-1);
		}
	}
	return cnt;
}

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