Submission #678404

#TimeUsernameProblemLanguageResultExecution timeMemory
678404jhwest2Virus Experiment (JOI19_virus)C++17
14 / 100
734 ms86916 KiB
#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], anc[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); anc[ax][ay] = anc[bx][by]; } par[bx][by] = a; for (auto v : vec[bx][by]) { bool f = true; auto [x, y] = v; for (int t = 0; t < 4; t++) { int nx = x + dx[t]; int ny = y + dy[t]; if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && Find({nx, ny}) != a) f = false; if (ok(nx, ny, a)) g[ax][ay].push_back({nx, ny}); } if (!f) vec[ax][ay].push_back(v); } 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; // new vertex if (!vis[nx][ny]) { vis[nx][ny] = 1; anc[nx][ny] = {s, t}; auto f = dfs(nx, ny); // if dfs(nx, ny) visits other scc, not a candidate if (!f) { bad[s][t] = 1; vis[x][y] = 2; return false; } } else if (vis[nx][ny] == 1) { // ancestor while (Find({nx, ny}) != Find({s, t})) { Union(anc[s][t], {s, t}); tie(s, t) = Find({s, t}); } } else { // visits other scc 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); } } } 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 (anc[i][j] != pair<int, int>(0, 0)) { auto [x, y] = anc[i][j]; bad[x][y] = 1; } } } // for (int i = 1; i <= n; i++) { // for (int j = 1; j <= m; j++) { // auto [x, y] = Find({i, j}); // cout << i << ' ' << j << ' ' << x << ' ' << y << '\n'; // } // } 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...