Submission #57356

#	Time	Username	Problem	Language	Result	Execution time	Memory
57356		thiago4532	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	103 ms	11312 KiB

rainbow

#include <bits/stdc++.h>
#include "rainbow.h"

using namespace std;
const int maxn = 2e5 + 10;
bool mat[3][maxn];
int n, m, pi, pj, rios[3][maxn], prefix[3][maxn];
bool mark[3][maxn];
int num;
int l[] = {-1, 1, 0, 0};
int c[] = {0, 0, -1, 1};

void dfs(int i, int j, int k){
	for(int mm=0;mm<4;mm++){
		int i2 = i + l[mm], j2 = j + c[mm];
		if(i2 < 1 || i2 > n || j2 < 1 || j2 > m || !mat[i2][j2] || mark[i2][j2]) continue;
		mark[i2][j2] = mark[i][j];
		//cout << "DFS x: " << n << " " << m  << " f " << k << " " << j << "\n";
		rios[k][j2] = rios[k][j];
		dfs(i2, j2, k);
	}
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	n = R, m = C;
	pi = sr, pj = sc;

	mat[sr][sc] = 1;	
	for(int i=0;i<M;i++){
		if(S[i] == 'N') --sr;
		else if(S[i] == 'S') ++sr;
		else if(S[i] == 'W') --sc;
		else if(S[i] == 'E') ++sc;

		mat[sr][sc] = 1;
	}
	memset(rios, -1, sizeof rios);
	rios[0][1] = rios[1][1] = rios[2][1] = 0;

	for(int i=1;i<=2;i++){
		memset(mark, 0, sizeof mark);
		num = 0;
		for(int j=2;j<=m;j++){
			if(rios[i][j] == -1) rios[i][j] = rios[i][j-1];

			if(mat[i][j]){
				if(!mark[i][j]){
					mark[i][j] = ++num;
					dfs(i, j, i);
				}else{
					j++;
					if(!mat[i][j] && j <= m) rios[i][j] = rios[i][j-2] + 1;
					continue;
				}
			

				while(j <= m && mat[i][j]){
					rios[i][j] = rios[i][j-1];
					j++;
				}
				if(j <= m) rios[i][j] = rios[i][j-1] + 1;
			}
		}
	}

	memset(mark, 0, sizeof mark);
	num = 0;
	for(int j=2;j<=m;j++){
		if(rios[0][j] == -1) rios[0][j] = rios[0][j-1];

		if(mat[1][j] && mat[2][j]){
			if(!mark[1][j]){
				mark[1][j] = ++num;
				dfs(1, j, 0);
			}else{
				j++;
				if(!mat[0][j] && j <= m) rios[0][j] = rios[0][j-2] + 1;
				continue;
			}
			
			while(j <= m && (mat[1][j] && mat[2][j])){
				rios[0][j] = rios[0][j-1];
				j++;
			}
			if(j <= m) rios[0][j] = rios[0][j-1] + 1;
		}
	}

	for(int i=1;i<=2;i++)
		for(int j=1;j<=m;j++)
			prefix[i][j] = prefix[i][j-1] + (mat[i][j]);

	for(int j=1;j<=m;j++)
		prefix[0][j] = prefix[0][j-1] + (mat[1][j] && mat[2][j]);

	// for(int i=0;i<=2;i++){
	// 	cout << i << ": "; 
	// 	for(int j=1;j<=m;j++)
	// 		cout << rios[i][j] << " \n"[j==m];
	// }
	// cout << "\n";
	// for(int i=0;i<=2;i++){
	// 	cout << i << ": "; 
	// 	for(int j=1;j<=m;j++)
	// 		cout << prefix[i][j] << " \n"[j==m];
	// }
}

int colour(int ar, int ac, int br, int bc) {
	if(ar == br){
		return (prefix[ar][bc] - prefix[ar][ac-1] == bc - ac + 1 ? 0 : rios[ar][bc] - rios[ar][ac] + 1);
	}else{
		return (prefix[0][bc] - prefix[0][ac-1] == bc - ac + 1 ? 0 :  rios[0][bc] - rios[0][ac] + 1);
	}
    return 0;
}

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