Submission #400446

#	Time	Username	Problem	Language	Result	Execution time	Memory
400446		timmyfeng	Virus Experiment (JOI19_virus)	C++17	100 / 100	890 ms	173056 KiB

virus

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

const int I[] = {1, 0, -1, 0}, J[] = {0, 1, 0, -1};
const string D = "SENW";

const int N = 800;

int resist[N][N], wind[1 << 4], r, c;

int visited[N * N], in_path[N * N], color[N * N];
vector<int> scc[N * N], adj[N * N], path;

bool check(int i, int j, int k) {
    int mask = 0;
    for (int d = 0; d < 4; ++d) {
        int i_new = i + I[d], j_new = j + J[d];
        if (0 <= i_new && i_new < r && 0 <= j_new && j_new < c) {
            if (color[i_new * c + j_new] == k) {
                mask |= 1 << d;
            }
        }
    }
    return resist[i][j] > 0 && resist[i][j] <= wind[mask];
}

void process(vector<int> &nodes, vector<int> &out) {
    for (auto u : nodes) {
        int i = u / c, j = u % c;
        for (int d = 0; d < 4; ++d) {
            int i_new = i + I[d], j_new = j + J[d];
            if (0 <= i_new && i_new < r && 0 <= j_new && j_new < c) {
                if (check(i_new, j_new, color[u])) {
                    out.push_back(i_new * c + j_new);
                }
            }
        }
    }
}

void dfs(int u) {
    visited[u] = in_path[u] = true;
    path.push_back(color[u]);

    for (int i = 0; i < (int) adj[u].size(); ++i) {
        int c = adj[u][i];

        if (!visited[c]) {
            dfs(c);

            if (color[u] != path.back()) {
                for (auto v : scc[path.back()]) {
                    in_path[v] = false;
                }
                path.pop_back();
            }
        } else if (in_path[c]) {
            int x = path.back();
            path.pop_back();

            while (color[c] != x) {
                int y = path.back();
                path.pop_back();

                if (scc[x].size() < scc[y].size()) {
                    swap(x, y);
                }

                for (auto v : scc[y]) {
                    color[v] = x;
                }

                scc[x].insert(scc[x].end(), scc[y].begin(), scc[y].end());
                process(scc[y], adj[u]);
                scc[y].clear();
            }

            path.push_back(x);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    string d;
    cin >> m >> r >> c >> d;

    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            cin >> resist[i][j];
        }
    }

    for (int i = 0; i < (1 << 4); ++i) {
        int len = 0;
        for (int j = 0; j < 2 * m; ++j) {
            int dir = find(D.begin(), D.end(), d[j % m]) - D.begin();
            if ((i & (1 << dir)) > 0) {
                wind[i] = max(wind[i], ++len);
            } else {
                len = 0;
            }
        }

        if (len == 2 * m) {
            wind[i] = INT_MAX;
        }
    }

    iota(color, color + r * c, 0);
    for (int i = 0; i < r * c; ++i) {
        scc[i] = {i};
        process(scc[i], adj[i]);
    }

    for (int i = 0; i < r * c; ++i) {
        if (visited[i] == 0) {
            dfs(i);
            for (auto j : scc[path.back()]) {
                in_path[j] = false;
            }
            path.pop_back();
        }
    }

    map<int, char> ids;
    set<pair<char, char>> edges;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (ids.count(color[i * c + j]) == 0) {
                ids[color[i * c + j]] = 'a' + (int) ids.size();
            }
        }
    }

    int mini = INT_MAX, ways = 0;
    for (int i = 0; i < r * c; ++i) {
        bool leaf = !scc[i].empty();
        for (auto j : scc[i]) {
            for (auto k : adj[j]) {
                leaf &= color[k] == i;

                if (i != color[k]) {
                    edges.insert({ids[i], ids[color[k]]});
                }
            }
        }

        if (leaf && resist[i / c][i % c] > 0) {
            if ((int) scc[i].size() < mini) {
                mini = scc[i].size();
                ways = 0;
            }

            if ((int) scc[i].size() == mini) {
                ways += mini;
            }
        }
    }

    cout << mini << "\n";
    cout << ways << "\n";
}

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