Submission #139232

#	Time	Username	Problem	Language	Result	Execution time	Memory
139232		Minnakhmetov	Virus Experiment (JOI19_virus)	C++14	100 / 100	334 ms	35032 KiB

virus

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int N = 805, M = 2e5 + 5, C = N * N, INF = 1e9;
const char dir[5] = "WESN";
const int dx[4] = { 0, 0, -1, 1 }, dy[4] = { 1, -1, 0, 0 };
int u[N][N], mx_seq[1 << 4], a[M], used[N][N], q[C], mask[N][N], last_us[N][N], comp[N][N], ans[N][N];
bool isSpec[N][N], isDead[C];
pair<int, int> comp_spec[C];

int st_cnt = 0, m, r, c;

int findSet(int v) {
    return q[v] < 0 ? v : q[v] = findSet(q[v]);
}

int toNum(int x, int y) {
    return x * c + y;
}

void connect(int a, int b) {
    a = findSet(a);
    b = findSet(b);

    isSpec[comp_spec[a].first][comp_spec[a].second] = false;

    auto spec = comp_spec[b];

    if (q[a] > q[b])
        swap(a, b);

    isDead[a] = isDead[a] || isDead[b];
    q[a] += q[b];
    q[b] = a;
    comp_spec[a] = spec;
    comp[spec.first][spec.second] = a;
}

bool bfs(int sx, int sy) {
    queue<pair<int, int>> q;
    q.push({sx, sy});
    used[sx][sy] = ++st_cnt;

    int cur_comp = findSet(toNum(sx, sy)),
        infected_count = 1;

    vector<pair<int, int>> visited;

    while (!q.empty()) {
        pair<int, int> node = q.front();
        q.pop();

        visited.push_back(node);

        for (int i = 0; i < 4; i++) {
            int x = node.first + dx[i],
                y = node.second + dy[i];


            if (x >= 0 && x < r && y >= 0 && y < c && 
                used[x][y] != st_cnt) {

                if (last_us[x][y] != st_cnt) {
                    mask[x][y] = 0;
                    last_us[x][y] = st_cnt;
                }

                mask[x][y] |= 1 << i;

                // cout << node.first << " " << node.second << " " << x << " " << y << "\n";

                if (mx_seq[mask[x][y]] >= u[x][y]) {
                    int oth_comp = findSet(toNum(x, y));

                    if (oth_comp != cur_comp) {
                        connect(cur_comp, oth_comp);
                        return false;
                    }

                    infected_count++;
                    used[x][y] = st_cnt;
                    q.push({x, y});
                }
            }
        }
    }

    for (auto p : visited) {
        ans[p.first][p.second] = infected_count;
    }

    return true;
}

signed main() { 
#ifdef HOME
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string s;
    

    cin >> m >> r >> c >> s;

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

            isSpec[i][j] = 1;
            comp[i][j] = toNum(i, j);
            comp_spec[comp[i][j]] = { i, j };
            if (u[i][j] == 0)
                u[i][j] = INF + 1;
            ans[i][j] = INF;
        }
    }

    for (char &c : s) {
        c = find(dir, dir + 4, c) - dir;
    }

    s += s;
    m *= 2;

    for (int i = 0; i < (1 << 4); i++) {
        for (int j = 0; j < m; j++) {
            a[j] = (i >> s[j]) & 1;
        }
        for (int j = 0, k = -1; j < m; j++) {
            if (a[j]) {
                if (j == m - 1 || a[j + 1] == 0)
                    mx_seq[i] = max(mx_seq[i], j - k);
            }
            else {
                k = j;
            }
        }
        if (mx_seq[i] == m)
            mx_seq[i] = INF;
    }

    fill(q, q + C, -1);

    bool work = true;

    while (work) {
        work = false;

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (isSpec[i][j] && !isDead[comp[i][j]] && u[i][j] < INF) {
                    if (bfs(i, j))
                        isDead[comp[i][j]] = 1;
                    else
                        work = true;
                }
            }
        }

        // for (int x = 0; x < r; x++) {
        //     for (int y = 0; y < c; y++) {
        //         cout << findSet(toNum(x, y)) << " ";
        //     }
        //     cout << "\n";
        // }
        // cout << "\n";
        // for (int x = 0; x < r; x++) {
        //     for (int y = 0; y < c; y++) {
        //         cout << ans[x][y] << " ";
        //     }
        //     cout << "\n";
        // }
        // cout << "\n";
        // for (int x = 0; x < r; x++) {
        //     for (int y = 0; y < c; y++) {
        //         cout << isDead[findSet(toNum(x, y))] << " ";
        //     }
        //     cout << "\n";
        // }
        // cout << "\n";
        // cout << "\n";
        // cout << "\n";
    }


    int mn = INF, ct = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (ans[i][j] < mn) {
                mn = ans[i][j];
                ct = 0;
            }
            if (ans[i][j] == mn) {
                ct++;
            }
        }
    }

    cout << mn << "\n" << ct;


    return 0;
}

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