Submission #1117075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117075		mmk	Land of the Rainbow Gold (APIO17_rainbow)	C++14	11 / 100	19 ms	760 KiB

rainbow

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

const int MAXN = 60;

int grid[MAXN][MAXN], marc[MAXN][MAXN];

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

bool valid(int x, int y, pair<int,int> tleft, pair<int,int> bright)
{
    if(x <= 0 || x > 50 || x < tleft.first || x > bright.first) return false;
    if(y <= 0 || y > 50 || y < tleft.second || y > bright.second) return false;
    if(grid[x][y] == -1 || marc[x][y]) return false;
    return true;
}

void dfs(int x, int y, pair<int,int> tleft, pair<int,int> bright)
{
    // cerr << x << " " << y << "||\n";
    marc[x][y] = 1;

    for(int k = 0; k < 4; k++)
    {
        int nx = x + dx[k];
        int ny = y + dy[k];

        if(valid(nx,ny,tleft,bright))
        {
            dfs(nx,ny,tleft,bright);
        }
    }
}

int contaComp(pair<int,int> tleft, pair<int,int> bright)
{
    // int x = tleft.first, y = tleft.second;
    // int cnt = 0;

    // cerr << "\n=========\n";

    for(int i = 0; i <= 55; i++)
    {
        for(int j = 0; j <= 55; j++)
            marc[i][j] = 0;
    }

    int resp = 0;
    for(int i = tleft.first; i <= bright.first; i++)
    {
        for(int j = tleft.second; j <= bright.second; j++)
        {
            if(grid[i][j] == -1) continue;
            if(!marc[i][j])
            {
                dfs(i,j,tleft,bright);
                // cerr << "\n";
                resp++;
            }
        }
    }
    // cerr << "=========\n";

    return resp;
}

void init(int R, int C, int sr, int sc, int M, char *S)
{
    int x = sr, y = sc;
    grid[sr][sc] = -1;
    for(int i = 0; i < M; i++)
    {
        x -= (S[i] == 'N');
        x += (S[i] == 'S');


        y -= (S[i] == 'W');
        y += (S[i] == 'E');

        // cerr << x << " " << y << " COBRA \n";
        grid[x][y] = -1;
    }
}

int colour(int ar, int ac, int br, int bc)
{
    return contaComp({ar,ac},{br,bc});
}

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