#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
// https://github.com/Aeren1564/Algorithms
template<bool Enable_small_to_large = true>
struct disjoint_set {
int n, cc;
vector<int> p;
disjoint_set(int n): n(n), p(n, -1), cc(n) { }
int root(int u) {
return p[u] < 0 ? u : p[u] = root(p[u]);
}
bool share(int a, int b) {
return root(a) == root(b);
}
int size(int u) {
return -p[root(u)];
}
bool merge(int u, int v) {
u = root(u), v = root(v);
if(u == v) return false;
if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
p[u] += p[v], p[v] = u; cc--;
return true;
}
void clear() {
fill(p.begin(), p.end(), -1);
}
vector<vector<int>> group_up() {
vector<vector<int>> g(n);
for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
return g;
}
};
const int MXN = 53;
const vector<array<int, 2>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool f[MXN][MXN];
int n, m;
int con(int i, int j) {
return m * i + j;
}
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R, m = C;
int x = sr - 1, y = sc - 1;
f[x][y] = true;
for(int i = 0; i < M; i++) {
char c = S[i];
if(c == 'N')
x--;
else if(c == 'S')
x++;
else if(c == 'W')
y--;
else
y++;
//cout << x + 1 << ' ' << y + 1 << '\n';
f[x][y] = true;
}
}
int colour(int ar, int ac, int br, int bc) {
vector<bool> vis(n * m);
ar--, ac--, br--, bc--;
function<void(int, int)> dfs = [&] (int i, int j) {
if(vis[con(i, j)])
return;
vis[con(i, j)] = true;
//cout << i + 1 << ' ' << j + 1 << '\n';
for(auto &[dx, dy] : dir) {
int nx = i + dx, ny = j + dy;
if(ar <= nx && nx <= br && ac <= ny && ny <= bc && !f[nx][ny])
dfs(nx, ny);
}
};
int cnt = 0;
for(int i = ar; i <= br; i++)
for(int j = ac; j <= bc; j++) if(!f[i][j] && !vis[con(i, j)]) {
cnt++;
//cout << "ok: " << cnt << endl;
dfs(i, j);
}
//cout << cnt << '\n';
return cnt;
}
#ifdef saarang
static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];
int main() {
scanf("%d %d %d %d", &R, &C, &M, &Q);
scanf("%d %d", &sr, &sc);
if (M > 0) {
scanf(" %s ", S);
}
init(R, C, sr, sc, M, S);
int query;
for (query = 0; query < Q; query++) {
int ar, ac, br, bc;
scanf("%d %d %d %d", &ar, &ac, &br, &bc);
printf("%d\n", colour(ar, ac, br, bc));
}
return 0;
}
#endif
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
212 KB |
Output is correct |
2 |
Correct |
9 ms |
212 KB |
Output is correct |
3 |
Correct |
33 ms |
468 KB |
Output is correct |
4 |
Correct |
34 ms |
432 KB |
Output is correct |
5 |
Correct |
8 ms |
372 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
24 ms |
424 KB |
Output is correct |
12 |
Correct |
22 ms |
340 KB |
Output is correct |
13 |
Correct |
11 ms |
368 KB |
Output is correct |
14 |
Correct |
6 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Runtime error |
2 ms |
624 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
212 KB |
Output is correct |
2 |
Correct |
9 ms |
212 KB |
Output is correct |
3 |
Correct |
33 ms |
468 KB |
Output is correct |
4 |
Correct |
34 ms |
432 KB |
Output is correct |
5 |
Correct |
8 ms |
372 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
24 ms |
424 KB |
Output is correct |
12 |
Correct |
22 ms |
340 KB |
Output is correct |
13 |
Correct |
11 ms |
368 KB |
Output is correct |
14 |
Correct |
6 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Execution timed out |
3081 ms |
4648 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
212 KB |
Output is correct |
2 |
Correct |
9 ms |
212 KB |
Output is correct |
3 |
Correct |
33 ms |
468 KB |
Output is correct |
4 |
Correct |
34 ms |
432 KB |
Output is correct |
5 |
Correct |
8 ms |
372 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
24 ms |
424 KB |
Output is correct |
12 |
Correct |
22 ms |
340 KB |
Output is correct |
13 |
Correct |
11 ms |
368 KB |
Output is correct |
14 |
Correct |
6 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Execution timed out |
3081 ms |
4648 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |