Submission #433480

#	Time	Username	Problem	Language	Result	Execution time	Memory
433480		rqi	Land of the Rainbow Gold (APIO17_rainbow)	C++14	11 / 100	31 ms	836 KiB

rainbow

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

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

#define mp make_pair
#define f first
#define s second
#define ins insert
#define pb push_back

void ckmin(int& a, int b){
	a = min(a, b);
}

void ckmax(int& a, int b){
	a = max(a, b);
}

vector<char> dchar = vector<char>{'S', 'E', 'N', 'W'};
vi dx = vi{1, 0, -1, 0};
vi dy = vi{0, 1, 0, -1};

bool filled[55][55];

struct DSU{
	vi e;
	void init(int N){
		e = vi(N, -1);
	}

	int get(int a){
		if(e[a] < 0) return a;
		e[a] = get(e[a]);
		return e[a];
	}

	bool unite(int a, int b){
		a = get(a);
		b = get(b);
		if(a == b) return 0;
		if(-e[a] < -e[b]) swap(a, b);
		e[a]+=e[b];
		e[b] = a;
		return 1;
	}
};
void init(int R, int C, int sr, int sc, int M, char *S) {
	for(int i = 0; i <= M; i++){
		filled[sr][sc] = 1;
		if(i < M){
			for(int d = 0; d < 4; d++){
				if(S[i] == dchar[d]){
					sr+=dx[d];
					sc+=dy[d];
					break;
				}
			}
		}
	}
}

int colour(int ar, int ac, int br, int bc) {
	DSU dsu;
	dsu.init(55*55);
	for(int i = ar; i <= br; i++){
		for(int j = ac; j <= bc; j++){
			if(!filled[i][j]){
				for(int d = 0; d < 4; d++){
					int new_r = i+dx[d];
					int new_c = j+dy[d];
					if(ar <= new_r && new_r <= br && ac <= new_c && new_c <= bc && !filled[new_r][new_c]){
						dsu.unite(55*i+j, 55*new_r+new_c);
					}
				}
			}
		}
	}

	int ans = 0;
	for(int i = ar; i <= br; i++){
		for(int j = ac; j <= bc; j++){
			if(!filled[i][j]){
				if(dsu.get(55*i+j) == 55*i+j){
					ans++;
				}
			}
		}
	}
	return ans;
}

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