Submission #978989

#	Time	Username	Problem	Language	Result	Execution time	Memory
978989		Muhammad_Aneeq	Land of the Rainbow Gold (APIO17_rainbow)	C++17	11 / 100	3073 ms	15796 KiB

rainbow

#include "rainbow.h"
#include <set>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
int const N=2e5+10;
set<int>riv[N]={};
int r,c;
void init(int R, int C, int sr, int sc, int M, char *S) 
{
    riv[sr].insert(sc);
    for (int i=0;i<M;i++)
    {
        if (S[i]=='N')
            sr--;
        if (S[i]=='S')
            sr++;
        if (S[i]=='W')
            sc--;
        if (S[i]=='E')
            sc++;
        riv[sr].insert(sc);
    }
    r=R;
    c=C;
}
vector<int>di[2]={{-1,1,0,0},{0,0,-1,1}};
int colour(int ar, int ac, int br, int bc) 
{
    if (r<=1000&&c<=1000)
    {
        int ans=0;
        bool vis[r+10][c+10]={};
        for (int i=ar;i<=br;i++)
        {
            for (int j=ac;j<=bc;j++)
            {
                if (!vis[i][j]&&riv[i].find(j)==riv[i].end())
                {
                    ans++;
                    vis[i][j]=1;
                    queue<pair<int,int>>Q;
                    Q.push({i,j});
                    while (Q.size())
                    {
                        int i,j;
                        tie(i,j)=Q.front();
                        Q.pop();
                        for (int k=0;k<4;k++)
                        {
                            int x=i+di[0][k],y=j+di[1][k];
                            if (x>=ar&&x<=br&&y>=ac&&y<=bc&&!vis[x][y]&&riv[x].find(y)==riv[x].end())
                            {
                                vis[x][y]=1;
                                Q.push({x,y});
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
    return 0;
}

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