이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int N = 707070;
const int INF = 1e9 + 10;
int n, m, len, a[N], limit[1 << 4]; string s;
int encode(char c) {
if (c == 'S')
return 0;
else if (c == 'E')
return 1;
else if (c == 'N')
return 2;
else
return 3;
}
int f(int x, int y) {
return m * (x - 1) + (y - 1) + 1;
}
pair<int, int> g(int x) {
return { (x - 1) / m + 1, (x - 1) % m + 1 };
}
bool in(int x, int y) {
return (1 <= x && x <= n && 1 <= y && y <= m);
}
int par[N], anc[N], vis[N];
vector<int> cell[N], adj[N];
bool bad[N];
int Find(int a) {
return par[a] = (par[a] == a) ? a : Find(par[a]);
}
bool ok(int v, int r) { // check if cell v is reachable from component r
auto [x, y] = g(v);
if (!in(x, y) || a[v] == 0 || Find(v) == r)
return false;
int msk = 0;
for (int t = 0; t < 4; t++) {
int nx = x + dx[t];
int ny = y + dy[t];
int w = f(nx, ny);
if (in(nx, ny) && a[w] && Find(w) == r)
msk |= 1 << t;
}
return a[v] <= limit[msk];
}
void Union(int a, int b) {
a = Find(a); b = Find(b);
if (a != b) {
if (cell[a].size() < cell[b].size()) {
swap(a, b);
anc[a] = anc[b];
}
par[b] = a;
for (int v : cell[b]) {
cell[a].push_back(v);
auto [x, y] = g(v);
for (int t = 0; t < 4; t++) {
int nx = x + dx[t];
int ny = y + dy[t];
int w = f(nx, ny);
if (in(nx, ny) && ok(w, a))
adj[a].push_back(w);
}
}
vector<int>().swap(cell[b]);
vector<int>().swap(adj[b]);
}
}
bool dfs(int v) {
auto [x, y] = g(v);
for (int t = 0; t < 4; t++) {
int nx = x + dx[t];
int ny = y + dy[t];
int w = f(nx, ny);
if (in(nx, ny) && ok(w, v))
adj[v].push_back(w);
}
int s = Find(v);
while (!adj[s].empty()) {
int z = adj[s].back();
adj[s].pop_back();
if (!ok(z, s))
continue;
if (vis[z] == 0) {
vis[z] = 1;
anc[z] = v;
bool f = dfs(z);
if (!f) {
vis[v] = 2;
bad[s] = 1;
return false;
}
}
else if (vis[z] == 1) {
while (Find(s) != Find(z)) {
Union(anc[s], s);
s = Find(s);
}
}
else {
vis[v] = 2;
bad[s] = 1;
return false;
}
s = Find(v);
}
vis[v] = 2;
return true;
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> len >> n >> m >> s;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[f(i, j)];
s += s;
// upper bound for each direction set
for (int msk = 0; msk < (1 << 4); msk++) {
int cnt = 0, maxv = 0;
for (int i = 0; i < 2 * len; i++) {
if (msk >> encode(s[i]) & 1)
++cnt;
else {
maxv = max(maxv, cnt);
cnt = 0;
}
}
maxv = max(maxv, cnt);
if (cnt == 2 * len)
limit[msk] = INF;
else
limit[msk] = maxv;
}
for (int i = 1; i <= n * m; i++) {
par[i] = i;
cell[i].push_back(i);
}
for (int i = 1; i <= n * m; i++) {
if (a[i] && !vis[i]) {
vis[i] = 1;
dfs(i);
}
}
for (int i = 1; i <= n * m; i++)
if (a[i] && Find(i) == i)
bad[anc[i]] = 1;
map<int, int> mp;
for (int i = 1; i <= n * m; i++)
if (a[i] && Find(i) == i && !bad[i])
mp[cell[i].size()] += cell[i].size();
cout << mp.begin()->first << '\n';
cout << mp.begin()->second << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |