Submission #138825

#	Time	Username	Problem	Language	Result	Execution time	Memory
138825		Minnakhmetov	Virus Experiment (JOI19_virus)	C++14	6 / 100	273 ms	1688 KiB

virus

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

const int N = 2e5 + 5, Z = 51, INF = 2e9;

string s;
char dir[5] = "WESN";
int m, r, c;
int a[N], resistance[Z][Z], mask[Z][Z], infected[Z][Z], mx[1 << 16], 
        dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0};


int infected_count = 0, mn = INF, ct = 0;
queue<pair<int, int>> q;

void handle(int sx, int sy) {
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            infected[i][j] = 0;
            mask[i][j] = 0;
        }
    }

    infected_count = 1;

    q.push({sx, sy});

    infected[sx][sy] = 1;

    while (!q.empty()) {
        int x = q.front().first,
            y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int j = x + dx[i], k = y + dy[i];

            if (j >= 0 && j < r && k >= 0 && k < c && !infected[j][k] &&
                resistance[j][k] > 0) {

                mask[j][k] |= 1 << i;
                if (mx[mask[j][k]] >= resistance[j][k]) {
                    infected[j][k] = 1;
                    q.push({ j, k });

                    infected_count++;
                }
            }
        }

        // for (int i = 0; i < r; i++) {
        //     for (int j = 0; j< c; j++) {
        //         cout << infected[i][j];
        //     }
        //     cout << "\n";
        // }
        // cout << "\n";
        if (infected_count > mn)
            break;
    }

    while (!q.empty())
        q.pop();
}

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

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

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

    s += s;

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

        if (mx[i] == m + m)
            mx[i] = INF;
    }

    pair<int, int> order[Z * Z];

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> resistance[i][j];
            order[i * c + j] = { i, j };
        }
    }

    // handle(0, 1);

    // cout << infected_count << "\n";
    // return 0;

    mt19937 rnd(time(0));   
    shuffle(order, order + r * c, rnd);

    for (int x = 0; x < r * c; x++) {
        int i = order[x].first,
            j = order[x].second;

        if (resistance[i][j] != 0) {
            handle(i, j);

            if (infected_count < mn) {
                mn = infected_count;
                ct = 0;
            }
            if (infected_count == mn)
                ct++;
        }
    }

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

    return 0;
}

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