Submission #681899

#TimeUsernameProblemLanguageResultExecution timeMemory
681899nutellaVirus Experiment (JOI19_virus)C++17
100 / 100
364 ms56516 KiB
#include <bits/stdc++.h> using namespace std; constexpr int dx[]{-1, 0, 1, 0}, dy[]{0, 1, 0, -1}; struct DSU { vector<int> p, sz; vector<vector<int>> subtree; DSU() = default; DSU(int n) : p(n), sz(n, 1), subtree(n) { iota(p.begin(), p.end(), 0); for (int i = 0; i < n; ++i) { subtree[i] = {i}; } } int leader(int x) { return x == p[x] ? x : p[x] = leader(p[x]); } bool unite(int a, int b) { a = leader(a), b = leader(b); if (a == b) { return false; } if (sz[a] < sz[b]) { swap(a, b); } subtree[a].insert(subtree[a].end(), subtree[b].begin(), subtree[b].end()); subtree[b].clear(); p[b] = a; sz[a] += sz[b]; return true; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int M, n, m; cin >> M >> n >> m; string str; cin >> str; vector<int> s(M); for (int i = 0; i < M; ++i) { char c = str[i]; s[i] = c == 'N' ? 0 : c == 'E' ? 1 : c == 'S' ? 2 : 3; } vector u(n, vector<int>(m)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> u[i][j]; } } const int N = n * m; vector dead(16, vector(n, vector<bool>(m))); for (int mask = 1; mask < 16; ++mask) { vector<bool> yay(M); for (int i = 0; i < M; ++i) { if (mask >> s[i] & 1) { yay[i] = true; } } int mx = 0; int first = -1e9, last = -1e9; for (int i = 0, j = 0; i < M; i = j) { while (j < M && yay[i] == yay[j]) { j += 1; } if (yay[i]) { mx = max(mx, j - i); if (i == 0) { first = j - i; } else if (j == M) { last = j - i; } } } mx = max(mx, first + last); if (mx == M) { mx = numeric_limits<int>::max(); } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { dead[mask][i][j] = u[i][j] && u[i][j] <= mx; } } } DSU d(N); auto check = [&](int i, int j, int a) -> bool { int mask = 0; for (int k = 0; k < 4; ++k) { int ni = i + dx[k], nj = j + dy[k]; if (ni >= 0 && ni < n && nj >= 0 && nj < m && d.leader(ni * m + nj) == a) { mask |= 1 << k; } } return dead[mask][i][j]; }; int ans = numeric_limits<int>::max(); int cnt = 0; vector<bool> in_stk(N); vector was(n, vector<bool>(m)); for (int ii = 0; ii < n; ++ii) { for (int jj = 0; jj < m; ++jj) { if (was[ii][jj] || u[ii][jj] == 0) { continue; } vector<int> stk; vector<vector<int>> consider; int i = ii, j = jj; consider.push_back({i * m + j}); stk.push_back(i * m + j); was[i][j] = true; in_stk[i * m + j] = true; bool ok = true; while (!consider.back().empty()) { const int now = consider.back().back(); int x = now / m, y = now % m; bool pop = true; for (int k = 0; k < 4; ++k) { int nx = x + dx[k], ny = y + dy[k]; if (nx >= 0 && nx < n && ny >= 0 && ny < m) { const int to = nx * m + ny; if (d.leader(to) == d.leader(now)) { continue; } if (check(nx, ny, i * m + j)) { int lead = d.leader(nx * m + ny); if (in_stk[lead]) { int pnt = consider.size() - 1; for (; pnt >= 0; --pnt) { if (stk[pnt] == lead) { break; } } for (int p = pnt + 1; p < consider.size(); ++p) { if (consider[pnt].size() < consider[p].size()) { swap(consider[pnt], consider[p]); } for (int yy : consider[p]) { consider[pnt].push_back(yy); } } pair<int, int> mx = {-1, -1}; for (int p = pnt; p < stk.size(); ++p) { mx = max(mx, pair{int(d.subtree[stk[p]].size()), p}); } for (int p = pnt; p < consider.size(); ++p) { if (p != mx.second) { for (int yy: d.subtree[stk[p]]) { consider[pnt].push_back(yy); } } } for (int aa = pnt; aa < consider.size() - 1; ++aa) { d.unite(stk[aa], i * m + j); } for (int aa = pnt; aa < stk.size(); ++aa) { in_stk[stk[aa]] = false; } consider.resize(pnt + 1); stk.resize(pnt + 1); lead = d.leader(i * m + j); i = lead / m, j = lead % m; in_stk[lead] = true; stk[pnt] = lead; pop = false; break; } else if (was[nx][ny]) { ok = false; break; } else { consider.push_back(vector{nx * m + ny}); stk.push_back(nx * m + ny); i = nx, j = ny; was[i][j] = true; in_stk[i * m + j] = true; pop = false; break; } } } } if (!ok) { break; } if (pop) { consider.back().pop_back(); } } int lead = d.leader(i * m + j); if (ok) { int now = d.subtree[lead].size(); if (ans > now) { ans = now; cnt = now; } else if (ans == now) { cnt += now; } } for (int aa : stk) { in_stk[aa] = false; } } } cout << ans << '\n' << cnt << '\n'; return 0; }

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:169:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |                                 for (int p = pnt + 1; p < consider.size(); ++p) {
      |                                                       ~~^~~~~~~~~~~~~~~~~
virus.cpp:179:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |                                 for (int p = pnt; p < stk.size(); ++p) {
      |                                                   ~~^~~~~~~~~~~~
virus.cpp:183:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |                                 for (int p = pnt; p < consider.size(); ++p) {
      |                                                   ~~^~~~~~~~~~~~~~~~~
virus.cpp:191:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |                                 for (int aa = pnt; aa < consider.size() - 1; ++aa) {
      |                                                    ~~~^~~~~~~~~~~~~~~~~~~~~
virus.cpp:195:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |                                 for (int aa = pnt; aa < stk.size(); ++aa) {
      |                                                    ~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...