Submission #540797

#	Time	Username	Problem	Language	Result	Execution time	Memory
540797		LucaDantas	Land of the Rainbow Gold (APIO17_rainbow)	C++17	11 / 100	32 ms	836 KiB

rainbow

#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;

constexpr int maxn = 55*55, lado = 55;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

struct DSU {
	int pai[maxn], peso[maxn];
	void init() { for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1; }
	int find(int x) { return pai[x] == x ? x : pai[x] = find(pai[x]); }
	void join(int a, int b) {
		a = find(a), b = find(b);
		if(a == b) return;
		if(peso[a] < peso[b])
			swap(a, b);
		pai[b] = a;
		peso[a] += peso[b];
	}
} dsu;

bool mark[lado][lado];

void dfs(int x, int y, int here, int moves, char *S) {
	mark[x][y] = 1;
	if(here == moves) return;
	char c = S[here];
	if(c == 'N') dfs(x-1, y, here+1, moves, S);
	else if(c == 'S') dfs(x+1, y, here+1, moves, S);
	else if(c == 'W') dfs(x, y-1, here+1, moves, S);
	else if(c == 'E') dfs(x, y+1, here+1, moves, S);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	// if(max(R, C) > 50) assert(0);
	dfs(sr, sc, 0, M, S);
}

int get(int a, int b) { return a * (52) + b; }

int colour(int ar, int ac, int br, int bc) {
	dsu.init();
	for(int r = ar; r <= br; r++) {
		for(int c = ac; c <= bc; c++) {
			if(mark[r][c]) continue;
			for(int k = 0; k < 4; k++)
				if(!mark[r+dx[k]][c+dy[k]])
					dsu.join(get(r,c), get(r + dx[k], c + dy[k]));
		}
	}
	static vector<int> siuu; siuu.clear();
	for(int r = ar; r <= br; r++)
		for(int c = ac; c <= bc; c++)
			if(!mark[r][c])
				siuu.push_back(dsu.find(get(r, c)));
	sort(siuu.begin(), siuu.end());
	return unique(siuu.begin(), siuu.end()) - siuu.begin();
}

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