| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 775180 | CyberCow | Land of the Rainbow Gold (APIO17_rainbow) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rainbow.h"
#include <queue>
using namespace std;
const int N = 200005;
int color[3][N];
int st[N];
int st1[N];
int st2[N];
int calooooor[55][55];
int sttttttt[55][55];
int ent = 0;
void init(int R, int C, int sr, int sc, int M, char *S) {
if (R == 2)
ent = 1;
if (ent == 1)
{
color[sr][sc] = 1;
for (int i = 0; i < M; i++)
{
if (S[i] == 'W')
{
sc--;
}
if (S[i] == 'S')
{
sr++;
}
if (S[i] == 'E')
{
sc++;
}
if (S[i] == 'N')
{
sr--;
}
color[sr][sc] = 1;
}
if (color[1][1] == 0 || color[2][1] == 0)
st[1] = 1;
for (int i = 2; i <= C; i++)
{
if ((color[1][i] == 0 && color[1][i - 1] == 0) || (color[2][i] == 0 && color[2][i - 1] == 0))
st[i] = st[i - 1];
else
{
if (color[1][i] == 0 || color[2][i] == 0)
st[i] = st[i + 1];
else
st[i] = st[i - 1];
}
}
if (color[1][1] == 0)
st1[1] = 1;
for (int i = 2; i <= C; i++)
{
if (color[1][i] == 1)
st1[i] = st1[i - 1];
else if (color[1][i - 1] == 0)
st1[i] = st1[i - 1];
else
st1[i] = st1[i - 1] + 1;
}
if (color[2][1] == 0)
st2[1] = 1;
for (int i = 2; i <= C; i++)
{
if (color[2][i] == 1)
st2[i] = st2[i - 1];
else if (color[2][i - 1] == 0)
st2[i] = st2[i - 1];
else
st2[i] = st2[i - 1] + 1;
}
}
else
{
calooooor[sr][sc] = 1;
for (int i = 0; i < M; i++)
{
if (S[i] == 'W')
{
sc--;
}
if (S[i] == 'S')
{
sr++;
}
if (S[i] == 'E')
{
sc++;
}
if (S[i] == 'N')
{
sr--;
}
calooooor[sr][sc] = 1;
}
}
}
int colour(int ar, int ac, int br, int bc) {
if (ent == 1)
{
int qan = 0;
if (ar == 1 && br == 1)
{
if (color[1][ac] == color[1][ac - 1] && color[1][ac] == 0)
{
qan = st1[bc] - st1[ac - 1] + 1;
}
else
{
qan = st1[bc] - st1[ac - 1];
}
}
else if (ar == 2 && br == 2)
{
if (color[2][ac] == color[2][ac - 1] && color[2][ac] == 0)
{
qan = st2[bc] - st2[ac - 1] + 1;
}
else
{
qan = st2[bc] - st2[ac - 1];
}
}
else
{
if ((color[1][ac] == 0 && color[1][ac - 1] == 0) || (color[2][ac] == 0 && color[2][ac - 1] == 0))
{
qan = st2[bc] - st2[ac - 1] + 1;
}
else
{
qan = st2[bc] - st2[ac - 1];
}
}
return qan;
}
else
{
queue<pair<int, int>> q;
for (int i = ar; i <= br; i++)
{
for (int j = ac; j <= bc; j++)
{
sttttttt[i][j] = 0;
}
}
int qan = 0;
for (int i = ar; i <= br; i++)
{
for (int j = ac; j <= bc; j++)
{
if (sttttttt[i][j] == 0 && color[i][j] == 0)
{
qan++;
int qq = 0;
q.push({ i, j });
sttttttt[i][j] = 1;
while (!q.empty())
{
qq++;
int x = q.front().firsttttttt, y = q.front().second;
q.pop();
sttttttt[x][y] = 1;
if (x + 1 <= br && color[x + 1][y] == 0 && sttttttt[x + 1][y] == 0)
{
q.push({ x + 1, y });
sttttttt[x + 1][y] = 1;
}
if (x - 1 >= ar && color[x - 1][y] == 0 && sttttttt[x - 1][y] == 0)
{
q.push({ x - 1, y });
sttttttt[x - 1][y] = 1;
}
if (y + 1 <= bc && color[x][y + 1] == 0 && sttttttt[x][y + 1] == 0)
{
q.push({ x, y + 1 });
sttttttt[x][y + 1] = 1;
}
if (y - 1 >= ac && color[x][y - 1] == 0 && sttttttt[x][y - 1] == 0)
{
q.push({ x, y - 1 });
sttttttt[x][y - 1] = 1;
}
}
}
}
}
for (int i = ar; i <= br; i++)
{
for (int j = ac; j <= bc; j++)
{
sttttttt[i][j] = 0;
}
}
return qan;
}
}