Submission #347694

#	Time	Username	Problem	Language	Result	Execution time	Memory
347694		nicholask	Land of the Rainbow Gold (APIO17_rainbow)	C++14	11 / 100	28 ms	1004 KiB

rainbow

//#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool a[51][200001];
int dp[4][200001];
bool rr;
void init(int R, int C, int sr, int sc, int M, char *S) {
	a[sr][sc]=1;
	for (int i=0; i<M; i++){
		if (S[i]=='N') sr--;
		else if (S[i]=='E') sc++;
		else if (S[i]=='S') sr++;
		else if (S[i]=='W') sc--;
		a[sr][sc]=1;
	}
	/*
	if (R==2){
		rr=1;
		int cur[4]={};
		for (int i=1; i<=C; i++){
			if (i==1){
				if (!a[1][i]) dp[1][i]=cur[1]=1;
				if (!a[2][i]) dp[2][i]=cur[2]=1;
				if (!a[1][i]||!a[2][i]) dp[3][i]=cur[3]=1;
			} else {
				if (a[1][i-1]&&!a[1][i]){
					cur[1]++;
					dp[1][i]=cur[1];
				} else dp[1][i]=dp[1][i-1];
				if (a[2][i-1]&&!a[2][i]){
					cur[2]++;
					dp[2][i]=cur[2];
				} else dp[2][i]=dp[2][i-1];
				if (a[1][i-1]&&a[2][i-1]&&(!a[1][i]||!a[2][i])){
					cur[3]++;
					dp[3][i]=cur[3];
				} else dp[3][i]=dp[3][i-1];
			}
		}
	}
	*/
}
int colour(int ar, int ac, int br, int bc) {
    /*if (rr){
    	if (ar==br) return dp[ar][bc]-dp[ar][ac]+(!a[ar][ac]);
    	else return dp[3][bc]-dp[3][ac]+(!a[3][ac]||!a[3][bc]);
	} else {*/
		int ans=0;
		bool visited[51][51];
		for (int i=1; i<51; i++){
			for (int j=1; j<51; j++) visited[i][j]=0;
		}
		for (int i=ar; i<=br; i++){
			for (int j=ac; j<=bc; j++){
				if (visited[i][j]||a[i][j]) continue;
				visited[i][j]=1;
				ans++;
				queue <pair <int,int> > q;
				q.push({i,j});
				while (!q.empty()){
					pair <int,int> t=q.front();
					q.pop();
					for (int d=0; d<4; d++){
						t.first+=dx[d];
						t.second+=dy[d];
						if (t.first>=ar&&t.first<=br&&t.second>=ac&&t.second<=bc&&!visited[t.first][t.second]&&!a[t.first][t.second]){
							visited[t.first][t.second]=1;
							q.push({t.first,t.second});
						}
						t.first-=dx[d];
						t.second-=dy[d];
					}
				}
			}
		}
		return ans;
	//}
}

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