Submission #895572

#	Time	Username	Problem	Language	Result	Execution time	Memory
895572		Alcabel	Virus Experiment (JOI19_virus)	C++17	100 / 100	180 ms	14948 KiB

virus

#include <bits/stdc++.h>
using namespace std;

char dir[4] = {'N', 'E', 'S', 'W'};
int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
vector<vector<pair<int, int>>> par;

pair<int, int> getParent(pair<int, int> v) {
    if (par[v.first][v.second] != v) {
        par[v.first][v.second] = getParent(par[v.first][v.second]);
    }
    return par[v.first][v.second];
}

void solve() {
    int len, n, m;
    cin >> len >> n >> m;
    string s;
    cin >> s;
    vector<vector<int>> a(n, vector<int>(m));
    par.resize(n);
    for (int i = 0; i < n; ++i) {
        par[i].resize(m);
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
            a[i][j] = min(a[i][j], len);
            par[i][j] = {i, j};
        }
    }
    s += s;
    vector<int> longestSeg(1 << 4);
    for (int mask = 1; mask < (1 << 4); ++mask) {
        for (int i = 0, last = -1; i < 2 * len; ++i) {
            bool within = false;
            if (s[i] == 'N') {
                within = (mask & 1);
            } else if (s[i] == 'E') {
                within = (mask & 2);
            } else if (s[i] == 'S') {
                within = (mask & 4);
            } else {
                within = (mask & 8);
            }
            if (within) {
                longestSeg[mask] = max(longestSeg[mask], i - last);
            } else {
                last = i;
            }
        }
        longestSeg[mask] = min(longestSeg[mask], len);
        // cerr << "mask: " << mask << ", longest: " << longestSeg[mask] << '\n';
    }
    // cerr << "!\n";
    vector<vector<char>> term(n, vector<char>(m));
    vector<vector<int>> vis(n, vector<int>(m, -1));
    int tt = -1;
    queue<pair<int, int>> q;
    bool action = true;
    pair<int, int> ans = {n * m + 10, 0};
    while (action) {
        action = false;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (a[i][j] > 0 && getParent({i, j}) == make_pair(i, j) && !term[i][j]) {
                    // cerr << "(" << i << ' ' << j << ")\n";
                    action = true;
                    q.emplace(i, j);
                    pair<int, int> nxt = {-1, -1};
                    int cnt = 0;
                    ++tt;
                    while (!q.empty()) {
                        auto [r, c] = q.front();
                        q.pop();
                        if (vis[r][c] == tt) {
                            continue;
                        }
                        // cerr << r << ' ' << c << '\n';
                        vis[r][c] = tt;
                        ++cnt;
                        for (int d = 0; d < 4; ++d) {
                            int newR = r + dr[d], newC = c + dc[d];
                            if (newR >= 0 && newR < n && newC >= 0 && newC < m && a[newR][newC] > 0 && vis[newR][newC] < tt) {
                                // cerr << "newR: " << newR << ", newC
                                int mask = 0;
                                for (int _d = 0; _d < 4; ++_d) {
                                    int coverR = newR + dr[_d], coverC = newC + dc[_d];
                                    if (coverR >= 0 && coverR < n && coverC >= 0 && coverC < m && vis[coverR][coverC] == tt) {
                                        mask |= (1 << _d);
                                    }
                                }
                                // cerr << "newR: " << newR << ", newC: " << newC << ", mask: " << mask << '\n';
                                if (longestSeg[mask] >= a[newR][newC]) {
                                    if (getParent({newR, newC}) == make_pair(i, j)) {
                                        q.emplace(newR, newC);
                                    } else {
                                        nxt = getParent({newR, newC});
                                        break;
                                    }
                                }
                                
                            }
                        }
                        if (nxt.first != -1) {
                            break;
                        }
                    }
                    while (!q.empty()) { q.pop(); }
                    // cerr << "nxt: " << nxt.first << ' ' << nxt.second << '\n';
                    if (nxt.first == -1) {
                        // cerr << "!\n";
                        term[i][j] = true;
                        if (cnt < ans.first) {
                            ans = {cnt, 0};
                        }
                        if (cnt == ans.first) {
                            ans.second += cnt;
                        }
                    } else if (term[nxt.first][nxt.second]) {
                        term[i][j] = true;
                    } else {
                        par[i][j] = nxt;
                    }
                }
            }
        }
    }
    cout << ans.first << ' ' << ans.second << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 6 / 6
• Subtask 3: 80 / 80