Submission #111827

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

rainbow

#include "rainbow.h"
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <iostream>

using namespace std;

const int MAX_N = 50;

typedef long long ll;
typedef pair<int, int> pii;

bool chk[MAX_N+1][MAX_N+1];
int R, C;

void init(int r, int c, int sr, int sc, int M, char *S) {
	R = r; C = c;
	chk[sr][sc] = true;
	for(int i=0; i<M; i++){
		if(S[i]=='N')	sr--;
		else if(S[i]=='E')	sc++;
		else if(S[i]=='W')	sc--;
		else sr++;
		//cout<<sr<<" "<<sc<<endl;
		chk[sr][sc] = true;
	}
}

bool vst[MAX_N+1][MAX_N+1];

pii A, B;

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

void dfs(int x, int y){
	if(x<A.first || x>B.first|| y<A.second || y>B.second)	return;
	if(vst[x][y] || chk[x][y])	return;
	vst[x][y] = true;
	for(int i=0; i<4; i++){
		dfs(x+dx[i], y+dy[i]);
	}
}

int colour(int ar, int ac, int br, int bc) {
	A = {ar, ac}; B = {br, bc};
	for(int i=ar; i<=br; i++){
		for(int j=ac; j<=bc; j++){
			vst[i][j] = false;
		}
	}
	int ans = 0;
	for(int i=ar; i<=br; i++){
		for(int j=ac; j<=bc; j++){
			if(!chk[i][j] && !vst[i][j]){
				//cout<<i<<" "<<j<<endl;
				ans++;
				dfs(i, j);
			}
		}
	}
    return ans;
}

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