Submission #73492

#	Time	Username	Problem	Language	Result	Execution time	Memory
73492		FedericoS	Land of the Rainbow Gold (APIO17_rainbow)	C++14	0 / 100	6 ms	432 KiB

rainbow

#include "rainbow.h"
#include <iostream>
#include <assert.h>
#include <queue>
using namespace std;

bool B[3][200005];
bool V[3][200005];
int R,C;
int A[3][200005];
int P[3][2][200005];
bool B_old[55][55];
bool V_old[55][55];
int rmov[]={1,-1,0,0};
int cmov[]={0,0,1,-1};
queue<pair<int,int>> Q;

void init(int R_, int C_, int sr, int sc, int M, char *W) {

	R=R_;
	C=C_;

	if(R<51 and C<51){
	 
		B_old[sr][sc]=true;
	 
		for(int i=0;i<M;i++){
	 
			if(W[i]=='S')
				sr++;
			if(W[i]=='N')
				sr--;
			if(W[i]=='E')
				sc++;
			if(W[i]=='W')
				sc--;
	 
			B_old[sr][sc]=true;
		}

		return;
		
	}

	B[1][0]=B[2][0]=true;
	B[1][C+1]=B[2][C+1]=false;
	B[1][C+2]=B[2][C+2]=true;

	for(int k=0;k<3;k++){
		A[k][0]=-1;
		P[k][0][0]=-1;
		P[k][0][C+2]=-1;
		P[k][1][0]=-1;
		P[k][1][C+2]=-1;
	}

	B[sr][sc]=true;
	int cont=0;

	for(int i=0;i<M;i++){

		if(W[i]=='S')
			sr++;
		if(W[i]=='N')
			sr--;
		if(W[i]=='E')
			sc++;
		if(W[i]=='W')
			sc--;

		B[sr][sc]=true;
	}

	for(int r=1;r<R+1;r++)
		for(int i=1;i<C+3;i++)
			if(B[r][i] and !B[r][i-1])
				A[r-1][i]=-1;
			else if(!B[r][i] and B[r][i-1])
				A[r-1][i]=++cont;
			else
				A[r-1][i]=A[r-1][i-1];

	for(int i=1;i<C+3;i++)
		if((B[2][i]&B[1][i]) and !(B[2][i-1]&B[1][i-1]))
			A[2][i]=-1;
		else if(!(B[2][i]&B[1][i]) and (B[2][i-1]&B[1][i-1]))
			A[2][i]=++cont;
		else
			A[2][i]=A[2][i-1];

	for(int k=0;k<3;k++){
		for(int i=1;i<C+3;i++)
			P[k][0][i]=(A[k][i]==-1)?P[k][0][i-1]:A[k][i];
		for(int i=C+1;i>=0;i--)
			P[k][1][i]=(A[k][i]==-1)?P[k][1][i+1]:A[k][i];
	}

	for(int k=0;k<3;k++){
		int res;
		for(int i=C+1;i>=0;i--)
			if(P[k][0][i]==-1 and P[k][0][i+1]!=-1)
				res=P[k][0][i+1]-1;
		for(int i=C+1;i>=0;i--)
			if(P[k][0][i]==-1)
				P[k][0][i]=res;
	}
/*
	for(int k=0;k<3;k++){
		for(int i=0;i<C+3;i++)
			cout<<A[k][i]<<" ";
		cout<<endl;
	}

	for(int k=0;k<3;k++){
		for(int i=0;i<C+3;i++)
			cout<<P[k][0][i]<<" ";
		cout<<endl;
	}

	for(int k=0;k<3;k++){
		for(int i=0;i<C+3;i++)
			cout<<P[k][1][i]<<" ";
		cout<<endl;
	}*/
}

int colour(int ar, int ac, int br, int bc) {

	if(R<51 and C<51){
	 
		ar--;
		ac--;
		br--;
		bc--;
		int ans=0;
	 
		for(int i=0;i<R;i++)
			for(int j=0;j<C;j++)
				V_old[i][j]=B_old[i][j];
	 
	 
		for(int i=ar;i<=br;i++)
			for(int j=ac;j<=bc;j++)
				if(!V_old[i][j]){
	 
					ans++;
					while(Q.size())
						Q.pop();
					Q.push({i,j});
	 
					while(Q.size()){
	 
						pair<int,int> p=Q.front();
						Q.pop();
						if(V_old[p.first][p.second])
							continue;
						V_old[p.first][p.second]=true;
	 
						for(int m=0;m<4;m++)
							if(!V_old[p.first+rmov[m]][p.second+cmov[m]] and ar<=p.first+rmov[m] and p.first+rmov[m]<=br and ac<=p.second+cmov[m] and p.second+cmov[m]<=bc)
								Q.push({p.first+rmov[m],p.second+cmov[m]});
							
					}
					
				}
	 
	    return ans;
		
	}

	int k;

	if(ar==1 and br==1)
		k=0;
	else if(ar==2 and br==2)
		k=1;
	else if(ar==1 and br==2)
		k=2;
	else
		assert(false);

	return P[k][0][bc]-P[k][1][ac]+1;

}

Compilation message (stderr)

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:105:15: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
     P[k][0][i]=res;
     ~~~~~~~~~~^~~~

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