Submission #928956

#	Time	Username	Problem	Language	Result	Execution time	Memory
928956		hmm789	Land of the Rainbow Gold (APIO17_rainbow)	C++14	11 / 100	3084 ms	39860 KiB

rainbow

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

int a[50][200000];
bool v[50][200000];

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

void init(int R, int C, int sr, int sc, int M, char *S) {
	sr--; sc--;
	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;
	}
}

int colour(int ar, int ac, int br, int bc) {
    int ans = 0;
    ar--; ac--; br--; bc--;
    for(int i = ar; i <= br; i++) {
		for(int j = ac; j <= bc; j++) if(a[i][j] == 0 && v[i][j] == 0) {
			ans++;
			queue<pair<int, int>> q;
			q.push({i, j});
			v[i][j] = 1;
			while(!q.empty()) {
				pair<int, int> c = q.front();
				q.pop();
				for(int k = 0; k < 4; k++) {
					int nx = c.first+dx[k], ny = c.second+dy[k];
					if(nx < ar || nx > br || ny < ac || ny > bc) continue;
					if(a[nx][ny] == 1 || v[nx][ny] == 1) continue;
					v[nx][ny] = 1;
					q.push({nx, ny});
				}
			}
		}
	}
    for(int i = ar; i <= br; i++) for(int j = ac; j <= bc; j++) v[i][j] = 0;
    return ans;
}

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