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 <bits/stdc++.h>
using namespace std;
const int N = 808;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int n, m, k, a[N][N], limit[1 << 4]; string s;
int f(char c) {
if (c == 'S')
return 0;
if (c == 'E')
return 1;
if (c == 'N')
return 2;
return 3;
}
int vis[N][N];
bool bad[N][N];
vector<pair<int, int>> g[N][N], vec[N][N];
pair<int, int> par[N][N];
pair<int, int> Find(pair<int, int> a) {
auto [x, y] = a;
return par[x][y] = ((par[x][y] == a) ? par[x][y] : Find(par[x][y]));
}
bool ok(int x, int y, pair<int, int> r) {
if (x <= 0 || y <= 0 || x > n || y > m || a[x][y] == 0)
return false;
if (Find({x, y}) == r)
return false;
int msk = 0;
for (int t = 0; t < 4; t++) {
int nx = x + dx[t];
int ny = y + dy[t];
if (nx <= 0 || ny <= 0 || nx > n || ny > m)
continue;
if (Find({nx, ny}) == r)
msk |= 1 << t;
}
return a[x][y] <= limit[msk];
}
void Union(pair<int, int> a, pair<int, int> b) {
// cout << "UNION " << a.first << ' ' << a.second << ' ' << b.first << ' ' << b.second << '\n';
a = Find(a); b = Find(b);
if (a != b) {
auto [ax, ay] = a;
auto [bx, by] = b;
if (vec[ax][ay].size() < vec[bx][by].size()) {
swap(a, b);
swap(ax, bx);
swap(ay, by);
}
par[bx][by] = a;
for (auto v : vec[bx][by]) {
vec[ax][ay].push_back(v);
auto [x, y] = v;
for (int t = 0; t < 4; t++) {
int nx = x + dx[t];
int ny = y + dy[t];
if (ok(nx, ny, a))
g[ax][ay].push_back({nx, ny});
}
}
vector<pair<int, int>>().swap(g[bx][by]);
vector<pair<int, int>>().swap(vec[bx][by]);
}
}
bool dfs(int x, int y) {
// cout << "VISIT " << x << ' ' << y << "!\n";
for (int t = 0; t < 4; t++) {
int nx = x + dx[t];
int ny = y + dy[t];
if (ok(nx, ny, {x, y}))
g[x][y].push_back({nx, ny});
}
int s = x, t = y;
while (!g[s][t].empty()) {
auto [nx, ny] = g[s][t].back();
g[s][t].pop_back();
// cout << x << ' ' << y << ' ' << nx << ' '<< ny << '\n';
if (!ok(nx, ny, {s, t}))
continue;
if (!vis[nx][ny]) {
vis[nx][ny] = 1;
auto f = dfs(nx, ny);
if (!f) {
bad[s][t] = 1;
vis[x][y] = 2;
return false;
}
}
else if (vis[nx][ny] == 1)
Union({x, y}, {nx, ny});
else {
bad[s][t] = 1;
vis[x][y] = 2;
return false;
}
tie(s, t) = Find({x, y});
}
vis[x][y] = 2;
return true;
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> k >> n >> m >> s;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 0; i < (1 << 4); i++) {
int l = -1, r = 0, x = -1;
for (int j = 0; j < k; j++) {
if (i >> f(s[j]) & 1)
++r;
else {
if (l == -1)
l = r;
x = max(x, r);
r = 0;
}
}
if (x == -1 && r == 0)
limit[i] = 0;
else if (x == -1)
limit[i] = 1e9 + 10;
else
limit[i] = max(r + l, x);
}
// initialize uf
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == 0)
continue;
par[i][j] = {i, j};
vec[i][j].push_back({i, j});
}
}
// run dfs
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] && !vis[i][j]) {
// cout << i << ' ' << j << " START?\n";
vis[i][j] = 1;
dfs(i, j);
}
}
}
map<int, int> mp;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == 0)
continue;
if (Find({i, j}) != pair<int, int>{i, j})
continue;
if (!bad[i][j])
mp[vec[i][j].size()] += vec[i][j].size();
}
}
auto [x, y] = *mp.begin();
cout << x << '\n' << y;
}
Compilation message (stderr)
virus.cpp: In function 'std::pair<int, int> Find(std::pair<int, int>)':
virus.cpp:26:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
26 | auto [x, y] = a;
| ^
virus.cpp: In function 'void Union(std::pair<int, int>, std::pair<int, int>)':
virus.cpp:52:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
52 | auto [ax, ay] = a;
| ^
virus.cpp:53:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
53 | auto [bx, by] = b;
| ^
virus.cpp:65:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
65 | auto [x, y] = v;
| ^
virus.cpp: In function 'bool dfs(int, int)':
virus.cpp:93:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
93 | auto [nx, ny] = g[s][t].back();
| ^
virus.cpp: In function 'int main()':
virus.cpp:181:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
181 | auto [x, y] = *mp.begin();
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |