#include "rainbow.h"
#include <bits/stdc++.h>
void iterate(std::pair<int, int> &x, char c) {
if (c == 'N') {
--x.first;
}
if (c == 'S') {
++x.first;
}
if (c == 'E') {
++x.second;
}
if (c == 'W') {
--x.second;
}
}
struct UnionFind {
int n;
std::vector<int> data;
int components;
UnionFind(int n_) : n(n_), data(n, -1), components(n) {}
int find(int v) {
if (data[v] < 0) {
return v;
} else {
return data[v] = find(data[v]);
}
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) {
return;
}
if (data[a] > data[b]) {
std::swap(a, b);
}
data[a] += data[b];
data[b] = a;
--components;
}
int countGroups() {
return components;
}
};
int R, C, sR, sC, M;
std::string S;
int T;
std::map<std::pair<int, int>, bool> dataMap;
std::array<std::vector<std::pair<int, int>>, 2> landRanges;
std::vector<std::pair<int, int>> vxRanges;
void init(int r, int c, int sr, int sc, int m, char *s) {
--sr, --sc;
R = r;
C = c;
sR = sr;
sC = sc;
M = m;
S.resize(M);
for (int i = 0; i < M; ++i) {
S[i] = s[i];
}
// check...
if (R == 2) {
T = 2;
} else if (R <= 50 and C <= 50) {
T = 1;
} else {
T = 3;
}
auto add = [&](const std::pair<int, int> &v, bool type) {
if (type) {
dataMap[v] = true;
} else {
if (dataMap.find(v) == dataMap.end()) {
dataMap[v] = false;
}
}
};
std::pair<int, int> p = {sR, sC};
if (T == 2) {
add(p, true);
for (int i = 0; i < M; ++i) {
iterate(p, S[i]);
add(p, true);
};
for (int x = 0; x < 2; ++x) {
int l = 0;
for (int i = 0; i < C; ++i) {
if (dataMap[{x, i}]) {
if (l != i) {
landRanges[x].push_back({l, i - l});
}
l = i + 1;
}
}
if (l != C) {
landRanges[x].push_back({l, C - l});
}
}
int l = 0;
for (int i = 0; i < C; ++i) {
if (dataMap[{0, i}] and dataMap[{1, i}]) {
if (l != i) {
vxRanges.push_back({l, i - l});
}
l = i + 1;
}
}
if (l != C) {
vxRanges.push_back({l, C - l});
}
} else {
auto addBlock = [&](const std::pair<int, int> &v) {
add(v, true);
for (int ax = -1; ax <= 1; ++ax) {
for (int ay = -1; ay <= 1; ++ay) {
if (ax == 0 and ay == 0) {
continue;
}
if (v.first + ax < 0 or v.first + ax >= R or v.second + ay < 0 or v.second + ay >= C) {
continue;
}
add({v.first + ax, v.second + ay}, false);
}
}
};
addBlock(p);
for (int i = 0; i < M; ++i) {
iterate(p, S[i]);
addBlock(p);
}
}
}
int colour(int ar, int ac, int br, int bc) {
--ar, --ac;
if (T == 2) {
const auto &ranges = (br - ar != 2 ? landRanges[ar] : vxRanges);
auto itr = std::upper_bound(ranges.begin(), ranges.end(), std::make_pair(ac, 0));
if (itr != ranges.begin()) {
--itr;
if (itr->first + itr->second <= ar) {
++itr;
}
}
auto itr2 = std::lower_bound(ranges.begin(), ranges.end(), std::make_pair(bc, 0));
return itr2 - itr;
} else {
std::map<std::pair<int, int>, int> blockId;
int id = 0;
int countRiver = 0;
for (const auto &[pos, type] : dataMap) {
const auto &[x, y] = pos;
if (ar <= x and x < br and ac <= y and y < bc) {
blockId[pos] = id++;
if (type) {
++countRiver;
}
}
}
UnionFind uft(id);
for (const auto &[p, i] : blockId) {
if (dataMap[p]) {
continue;
}
const auto &[x, y] = p;
for (int ax = -1; ax <= 1; ++ax) {
for (int ay = -1; ay <= 1; ++ay) {
if (ax != 0 and ay != 0) {
continue;
}
if (ax == 0 and ay == 0) {
continue;
}
const int nx = x + ax, ny = y + ay;
auto itr = blockId.find({nx, ny});
if (itr == blockId.end()) {
continue;
}
if (not dataMap[itr->first]) {
uft.merge(i, itr->second);
}
}
}
}
return uft.countGroups() - countRiver;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
167 ms |
26088 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
371 ms |
29188 KB |
Output is correct |
| 3 |
Correct |
336 ms |
29148 KB |
Output is correct |
| 4 |
Correct |
445 ms |
39292 KB |
Output is correct |
| 5 |
Correct |
249 ms |
21856 KB |
Output is correct |
| 6 |
Incorrect |
59 ms |
2580 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
